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:
HttpClient 4 – Follow Redirects for POST
Java Program to Implement Disjoint Set Data Structure
Java Program to Perform Search in a BST
Toán tử instanceof trong java
Java Program to Implement Interpolation Search Algorithm
Using a Spring Cloud App Starter
Hướng dẫn sử dụng luồng vào ra ký tự trong Java
Java Program to Implement Ford–Fulkerson Algorithm
Abstract class và Interface trong Java
Java Program to Implement Variable length array
Từ khóa throw và throws trong Java
Java Program to Generate Randomized Sequence of Given Range of Numbers
New Features in Java 12
Java Program to Implement PriorityBlockingQueue API
Spring Security Authentication Provider
Working with Network Interfaces in Java
Testing an OAuth Secured API with Spring MVC
Quick Intro to Spring Cloud Configuration
Merging Two Maps with Java 8
Logout in an OAuth Secured Application
Spring WebClient Filters
How to Get the Last Element of a Stream in Java?
Instance Profile Credentials using Spring Cloud
Java NIO2 Path API
Java Switch Statement
Java Program to Perform Insertion in a BST
Java Program to Implement CopyOnWriteArrayList API
Running Spring Boot Applications With Minikube
Converting Strings to Enums in Java
Java Program to Implement ConcurrentHashMap API
Lập trình đa luồng với CompletableFuture trong Java 8
Spring MVC Content Negotiation