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 Find kth Smallest Element by the Method of Partitioning the Array
JUnit 5 @Test Annotation
Integer Constant Pool trong Java
Introduction to Project Reactor Bus
ExecutorService – Waiting for Threads to Finish
Java Program to Implement Sparse Array
Spring Boot - File Handling
Guide to the ConcurrentSkipListMap
Rest Web service: Filter và Interceptor với Jersey 2.x (P1)
Java Scanner hasNext() vs. hasNextLine()
Java Program to Check Multiplicability of Two Matrices
REST Pagination in Spring
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Setting the Java Version in Maven
Using Optional with Jackson
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Using Java Assertions
Java Program to subtract two large numbers using Linked Lists
Java Program to Implement JobStateReasons API
Hướng dẫn Java Design Pattern – Prototype
Java Program to Generate Randomized Sequence of Given Range of Numbers
Mảng (Array) trong Java
Java Program to Implement ConcurrentLinkedQueue API
Debug a HttpURLConnection problem
Spring MVC + Thymeleaf 3.0: New Features
Spring 5 Testing with @EnabledIf Annotation
Java Program to implement Sparse Vector
Feign – Tạo ứng dụng Java RESTful Client
Guide to the Volatile Keyword in Java
How To Serialize and Deserialize Enums with Jackson
A Guide to TreeMap in Java
Java Program to find the maximum subarray sum using Binary Search approach