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:
Spring MVC and the @ModelAttribute Annotation
Java Program to Implement Red Black Tree
Java – Get Random Item/Element From a List
Java Program to Generate a Random UnDirected Graph for a Given Number of Edges
Properties with Spring and Spring Boot
Case-Insensitive String Matching in Java
Spring Boot - Zuul Proxy Server and Routing
Hướng dẫn Java Design Pattern – Strategy
String Initialization in Java
So sánh ArrayList và LinkedList trong Java
Java Program to Implement Merge Sort Algorithm on Linked List
Jackson Annotation Examples
Jackson – Bidirectional Relationships
Java Program to Implement Sorted Array
Giới thiệu thư viện Apache Commons Chain
@Before vs @BeforeClass vs @BeforeEach vs @BeforeAll
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Display Auto-Configuration Report in Spring Boot
Java Program to Implement Karatsuba Multiplication Algorithm
Java Program to Construct an Expression Tree for an Infix Expression
Java Program to Implement Ford–Fulkerson Algorithm
Java Program to Implement Dijkstra’s Algorithm using Queue
Template Engines for Spring
Guide to @JsonFormat in Jackson
Explain about URL and HTTPS protocol
Java Program for Douglas-Peucker Algorithm Implementation
Remove the First Element from a List
Send an email using the SMTP protocol
Java Program to Solve a Matching Problem for a Given Specific Case
Spring Boot Application as a Service
Returning Custom Status Codes from Spring Controllers
Iterable to Stream in Java