Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not

This is a java program to test whether a directed graph is weakly connected or not. The graph is weakly connected if it has more than one connected component.

Here is the source code of the Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

package com.sanfoundry.graph;
 
import java.util.*;
 
public class WeaklyConnectedGraph
{
    private int                 V;
    private int                 preCount;
    private int[]               low;
    private boolean[]           visited;
    private List<Integer>[]     graph;
    private List<List<Integer>> sccComp;
    private Stack<Integer>      stack;
 
    /** function to get all strongly connected components **/
    public List<List<Integer>> getSCComponents(List<Integer>[] graph)
    {
        V = graph.length;
        this.graph = graph;
        low = new int[V];
        visited = new boolean[V];
        stack = new Stack<Integer>();
        sccComp = new ArrayList<>();
        for (int v = 0; v < V; v++)
            if (!visited[v])
                dfs(v);
        return sccComp;
    }
 
    /** function dfs **/
    public void dfs(int v)
    {
        low[v] = preCount++;
        visited[v] = true;
        stack.push(v);
        int min = low[v];
        for (int w : graph[v])
        {
            if (!visited[w])
                dfs(w);
            if (low[w] < min)
                min = low[w];
        }
        if (min < low[v])
        {
            low[v] = min;
            return;
        }
        List<Integer> component = new ArrayList<Integer>();
        int w;
        do
        {
            w = stack.pop();
            component.add(w);
            low[w] = V;
        }
        while (w != v);
        sccComp.add(component);
    }
 
    @SuppressWarnings("unchecked")
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter number of Vertices");
        /** number of vertices **/
        int V = scan.nextInt();
        /** make graph **/
        List<Integer>[] g = new List[V];
        for (int i = 0; i < V; i++)
            g[i] = new ArrayList<Integer>();
        /** accept all edges **/
        System.out.println("Enter number of edges");
        int E = scan.nextInt();
        /** all edges **/
        System.out.println("Enter the edges in the graph : <from> <to>");
        for (int i = 0; i < E; i++)
        {
            int x = scan.nextInt();
            int y = scan.nextInt();
            g[x].add(y);
        }
        StronglyConnectedGraph t = new StronglyConnectedGraph();
        System.out.print("The graph is weakly connected? : ");
        /** print all strongly connected components **/
        List<List<Integer>> scComponents = t.getSCComponents(g);
        Iterator<List<Integer>> iterator = scComponents.iterator();
        boolean weaklyConnected = false;
        while (iterator.hasNext())
        {
            if (iterator.next().size() <= 1)
            {
                weaklyConnected = true;
            }
        }
        System.out.println(weaklyConnected);
        scan.close();
    }
}

Output:

$ javac WeaklyConnectedGraph.java
$ java WeaklyConnectedGraph
 
Enter number of Vertices
6
Enter number of edges
7
Enter the edges in the graph : <from> <to>
0 1
1 2
1 3
3 4
4 5
5 3
5 2
The graph is weakly connected? : true

Related posts:

Kết hợp Java Reflection và Java Annotations
Spring RestTemplate Error Handling
String Joiner trong Java 8
Java Program to Implement the Edmond’s Algorithm for Maximum Cardinality Matching
Creating Docker Images with Spring Boot
A Guide to Queries in Spring Data MongoDB
Java Program to Implement AA Tree
How to Read HTTP Headers in Spring REST Controllers
Spring Boot: Customize Whitelabel Error Page
Remove HTML tags from a file to extract only the TEXT
Hướng dẫn Java Design Pattern – Builder
Java Program to find the peak element of an array using Binary Search approach
Guide to DelayQueue
Java Program to Implement Direct Addressing Tables
Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range
Java Program to Implement CopyOnWriteArraySet API
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
Spring Boot - Batch Service
An Intro to Spring Cloud Task
Introduction to Spliterator in Java
Java Program to Check Whether a Given Point is in a Given Polygon
Java Program to Implement Binomial Heap
How to Set TLS Version in Apache HttpClient
RestTemplate Post Request with JSON
Java Program to Implement Hopcroft Algorithm
Java Program to Implement Trie
A Custom Media Type for a Spring REST API
Spring Boot - Actuator
Java Program to Perform integer Partition for a Specific Case
Java Program to Implement Min Hash
Java Program to do a Breadth First Search/Traversal on a graph non-recursively
Java Web Services – Jersey JAX-RS – REST và sử dụng REST API testing tools với Postman