This is a java program to test whether a directed graph is strongly connected or not. The graph is strongly connected if it has only one connected component.
Here is the source code of the Java Program to Test Using DFS Whether a Directed Graph is Strongly Connected or Not. 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.*; public class StronglyConnectedGraph { 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 strongly connected? : "); /** print all strongly connected components **/ List<List<Integer>> scComponents = t.getSCComponents(g); Iterator<List<Integer>> iterator = scComponents.iterator(); boolean stronglyConnected = true; while (iterator.hasNext()) { if (iterator.next().size() <= 1) { stronglyConnected = false; } } System.out.println(stronglyConnected); scan.close(); } }
Output:
$ javac StronglyConnectedGraph.java $ java StronglyConnectedGraph 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 strongly connected? : false Enter number of Vertices 8 Enter number of edges 14 Enter the edges in the graph : <from> <to> 0 1 1 2 2 3 3 2 3 7 7 3 2 6 7 6 5 6 6 5 1 5 4 5 4 0 1 4 The graph is strongly connected? : true
Related posts:
Truyền giá trị và tham chiếu trong java
Java Program to add two large numbers using Linked List
Default Password Encoder in Spring Security 5
Java Program to Check if an UnDirected Graph is a Tree or Not Using DFS
What is Thread-Safety and How to Achieve it?
File Upload with Spring MVC
Converting Strings to Enums in Java
Java Program to Describe the Representation of Graph using Incidence List
Using Spring ResponseEntity to Manipulate the HTTP Response
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Guide to WeakHashMap in Java
Checked and Unchecked Exceptions in Java
Merging Streams in Java
Java Program to Implement the Edmond’s Algorithm for Maximum Cardinality Matching
Hướng dẫn Java Design Pattern – Intercepting Filter
Guide to the Fork/Join Framework in Java
Guide to Selenium with JUnit / TestNG
Java Program to Implement Stack using Linked List
Debug a JavaMail Program
Sử dụng CountDownLatch trong Java
Giới thiệu thư viện Apache Commons Chain
Java Program to Implement Best-First Search
Java Program to Implement Brent Cycle Algorithm
Tính kế thừa (Inheritance) trong java
Vòng lặp for, while, do-while trong Java
Spring Security – Reset Your Password
How To Serialize and Deserialize Enums with Jackson
Vector trong Java
Spring Data Java 8 Support
Disable DNS caching
Java Program to Implement the Monoalphabetic Cypher
Spring Boot - Interceptor