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:
Java Program to Implement RoleUnresolvedList API
Check If a File or Directory Exists in Java
Java Program to Generate Random Hexadecimal Byte
Java Collections Interview Questions
HashSet trong Java hoạt động như thế nào?
Convert a Map to an Array, List or Set in Java
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Java InputStream to String
Java Program to Implement LinkedHashMap API
A Quick Guide to Spring MVC Matrix Variables
CharSequence vs. String in Java
Bootstrapping Hibernate 5 with Spring
Java CyclicBarrier vs CountDownLatch
Java Program to Implement Hash Tables Chaining with Doubly Linked Lists
Daemon Threads in Java
Converting Strings to Enums in Java
A Guide to Spring Cloud Netflix – Hystrix
Spring Boot - Rest Template
Java Program to Optimize Wire Length in Electrical Circuit
A Guide to the finalize Method in Java
Java Program to Perform Finite State Automaton based Search
Chuyển đổi Array sang ArrayList và ngược lại
Java Program to Find the GCD and LCM of two Numbers
Filtering a Stream of Optionals in Java
Remove the First Element from a List
Hướng dẫn Java Design Pattern – Object Pool
Most commonly used String methods in Java
Java Program to Implement Randomized Binary Search Tree
Send email with authentication
Shuffling Collections In Java
Java Program to Construct an Expression Tree for an Prefix Expression
Intro to the Jackson ObjectMapper