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:
Java Program to Implement Gabow Algorithm
A Guide to JUnit 5 Extensions
Java Program to Implement the Program Used in grep/egrep/fgrep
Spring Security and OpenID Connect
Java Program to Check Whether an Undirected Graph Contains a Eulerian Path
How to Use if/else Logic in Java 8 Streams
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Java – InputStream to Reader
Query Entities by Dates and Times with Spring Data JPA
Java Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree
What is a POJO Class?
Java Program to Implement LinkedHashMap API
Java Program to Implement Cubic convergence 1/pi Algorithm
A Guide to Java HashMap
Java Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph
Java Program to Implement LinkedList API
Java Program to Create a Random Linear Extension for a DAG
A Guide to JUnit 5
Java – Write an InputStream to a File
Java Deep Learning Essentials - Yusuke Sugomori
A Guide to @RepeatedTest in Junit 5
A Guide to Spring Boot Admin
Java equals() and hashCode() Contracts
Add Multiple Items to an Java ArrayList
The Modulo Operator in Java
Supplier trong Java 8
Hướng dẫn sử dụng String Format trong Java
How to Set TLS Version in Apache HttpClient
Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm
Inject Parameters into JUnit Jupiter Unit Tests
HttpClient Connection Management
New Features in Java 9