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
Setting Up Swagger 2 with a Spring REST API
Apache Tiles Integration with Spring MVC
Java Program to Perform String Matching Using String Library
A Guide to Queries in Spring Data MongoDB
Jackson – Decide What Fields Get Serialized/Deserialized
Setting the Java Version in Maven
Java Program to Check Whether Graph is DAG
How to Read a File in Java
Transactions with Spring and JPA
Java Program to Implement Control Table
Java Program to Perform Preorder Recursive Traversal of a Given Binary Tree
Guide to @ConfigurationProperties in Spring Boot
Tìm hiểu về Web Service
Java Program to Implement CopyOnWriteArrayList API
Jackson – JsonMappingException (No serializer found for class)
Java Program to Implement the Alexander Bogomolny’s UnOrdered Permutation Algorithm for Elements Fro...
Guide to Dynamic Tests in Junit 5
Comparing getPath(), getAbsolutePath(), and getCanonicalPath() in Java
Sử dụng CyclicBarrier trong Java
Introduction to Spring Cloud Stream
Hướng dẫn sử dụng luồng vào ra ký tự trong Java
XML-Based Injection in Spring
Java Program to Implement Threaded Binary Tree
Spring’s RequestBody and ResponseBody Annotations
Java Program to Implement Max Heap
Java Program to Check Whether a Directed Graph Contains a Eulerian Cycle
A Guide To UDP In Java
DistinctBy in the Java Stream API
Spring Boot Security Auto-Configuration
Java Program for Douglas-Peucker Algorithm Implementation
HttpClient Timeout