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:
Send email with JavaMail
Guide to the ConcurrentSkipListMap
Constructor Injection in Spring with Lombok
Introduction to Spring Cloud Stream
Spring Boot - OAuth2 with JWT
Hướng dẫn Java Design Pattern – Decorator
Handle EML file with JavaMail
Setting a Request Timeout for a Spring REST API
Java Program to Implement Karatsuba Multiplication Algorithm
Hướng dẫn Java Design Pattern – Null Object
Java Program to Implement Bresenham Line Algorithm
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Pagination and Sorting using Spring Data JPA
Serverless Functions with Spring Cloud Function
HttpClient Timeout
Removing all Nulls from a List in Java
Java Program to Implement Coppersmith Freivald’s Algorithm
Java Program to Implement Hash Tables
Java Program to Implement Fisher-Yates Algorithm for Array Shuffling
Spring Data – CrudRepository save() Method
Vòng lặp for, while, do-while trong Java
Remove All Occurrences of a Specific Value from a List
Semaphore trong Java
Java Program to Implement RoleList API
Quick Guide to Spring Bean Scopes
Java Program to Implement Multi-Threaded Version of Binary Search Tree
Phương thức forEach() trong java 8
Convert Character Array to String in Java
Send an email using the SMTP protocol
Java Program to Implement HashTable API
Java Program to Implement Queue using Linked List
Custom Exception trong Java