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:
XML Serialization and Deserialization with Jackson
Java Program to Print only Odd Numbered Levels of a Tree
Java Program to Find All Pairs Shortest Path
Java Program to Implement Horner Algorithm
Java Program to Implement Sorted Singly Linked List
Use Liquibase to Safely Evolve Your Database Schema
A Guide to System.exit()
Java Program to Check Cycle in a Graph using Topological Sort
Java Program to Implement Hash Tables Chaining with Doubly Linked Lists
Toán tử trong java
The DAO with Spring and Hibernate
Spring WebFlux Filters
Java Program to Find the Mode in a Data Set
Guide to Spring Cloud Kubernetes
Configure a Spring Boot Web Application
Simultaneous Spring WebClient Calls
Từ khóa this và super trong Java
Enum trong java
Java Perform to a 2D FFT Inplace Given a Complex 2D Array
Strongly Connected Components
Batch Processing with Spring Cloud Data Flow
Hướng dẫn Java Design Pattern – Composite
Adding Parameters to HttpClient Requests
Java Program to Implement Segment Tree
Check if a String is a Palindrome in Java
LIKE Queries in Spring JPA Repositories
Giới thiệu java.io.tmpdir
Lớp Properties trong java
So sánh HashSet, LinkedHashSet và TreeSet trong Java
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Posting with HttpClient
Java Program to implement Bi Directional Map