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:
Converting Strings to Enums in Java
Guide to the Volatile Keyword in Java
Giới thiệu Google Guice – Binding
Ignore Null Fields with Jackson
Introduction to Thread Pools in Java
Java Program to Implement Range Tree
Java – Byte Array to Reader
Java Program to Perform Partition of an Integer in All Possible Ways
Auditing with JPA, Hibernate, and Spring Data JPA
Introduction to Java 8 Streams
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Java Program to Implement RoleUnresolvedList API
Lập trình đa luồng với Callable và Future trong Java
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Control Structures in Java
Overview of the java.util.concurrent
Java Program to Check whether Directed Graph is Connected using DFS
Java Program to Find Minimum Element in an Array using Linear Search
Guide to CopyOnWriteArrayList
Tìm hiểu về Web Service
Java 8 StringJoiner
How to Delay Code Execution in Java
Java Program to Implement Kosaraju Algorithm
Create Java Applet to Simulate Any Sorting Technique
Java Convenience Factory Methods for Collections
Hướng dẫn Java Design Pattern – Singleton
Tính đa hình (Polymorphism) trong Java
Java Program to Perform Partial Key Search in a K-D Tree
Hướng dẫn sử dụng String Format trong Java
How to Convert List to Map in Java
Intersection of Two Lists in Java