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:
Java Program to Implement CopyOnWriteArraySet API
Hướng dẫn Java Design Pattern – Builder
HttpClient 4 – Follow Redirects for POST
Java Program to Implement Shoelace Algorithm
How to Count Duplicate Elements in Arraylist
Java Program to Implement Affine Cipher
Introduction to Netflix Archaius with Spring Cloud
Server-Sent Events in Spring
Spring Boot - Building RESTful Web Services
A Guide to System.exit()
Guide to Java OutputStream
Java Program to Represent Graph Using Linked List
Validate email address exists or not by Java Code
Check If Two Lists are Equal in Java
Spring RequestMapping
Java Program to Implement Hash Tables with Quadratic Probing
Java Program to Implement Counting Sort
Converting String to Stream of chars
Java Program to Check whether Undirected Graph is Connected using BFS
List Interface trong Java
Adding Parameters to HttpClient Requests
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
HttpClient Connection Management
Java Program to Describe the Representation of Graph using Adjacency Matrix
Comparing Strings in Java
Spring Cloud – Adding Angular
Guide to the ConcurrentSkipListMap
Converting String to Stream of chars
Java Program to Implement Triply Linked List
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
Spring Boot - Eureka Server