This is a java program to check whether a graph is strongly connected or weakly connected. If graph has more than one connected components it is weakly connected. If graph has only one connected component it is strongly connected.
Here is the source code of the Java Program to Check Whether it is Weakly Connected or Strongly Connected for a Directed Graph. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.maixuanviet.graph; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Scanner; import java.util.Stack; public class StronglyorWeaklyConnectedDigraphs { 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 : "); /** 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; } } if (weaklyConnected == true) System.out.println("Weakly Connected"); else System.out.println("Strongly Connected"); scan.close(); } }
Output:
$ javac StronglyorWeaklyConnectedDigraphs.java $ java StronglyorWeaklyConnectedDigraphs 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
Related posts:
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
List Interface trong Java
Hashtable trong java
Convert char to String in Java
Java toString() Method
Java Program to Check the Connectivity of Graph Using DFS
OAuth 2.0 Resource Server With Spring Security 5
Java Program to Perform Search in a BST
A Guide to the Java ExecutorService
Spring WebClient Filters
New Features in Java 11
Deque và ArrayDeque trong Java
The Java 8 Stream API Tutorial
Quick Guide to java.lang.System
Java Program to Find Number of Spanning Trees in a Complete Bipartite Graph
Simplify the DAO with Spring and Java Generics
Java Program to Implement Brent Cycle Algorithm
Dynamic Proxies in Java
Java Program to Implement Selection Sort
Java Program to Implement Hash Tree
Java Program to Implement Vector API
Java Program to Implement Treap
Optional trong Java 8
Simple Single Sign-On with Spring Security OAuth2
Generic Constructors in Java
Java Program to Compute Determinant of a Matrix
Arrays.asList vs new ArrayList(Arrays.asList())
Circular Dependencies in Spring
Java Program to Perform Encoding of a Message Using Matrix Multiplication
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Calling Stored Procedures from Spring Data JPA Repositories
Spring Cloud – Bootstrapping