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 Johnson’s Algorithm
Introduction to Spring Data MongoDB
Java Program to Find a Good Feedback Vertex Set
Java Program to Implement Graph Structured Stack
Using a Mutex Object in Java
Converting Strings to Enums in Java
Ignore Null Fields with Jackson
Spring Boot - Service Components
How to Read HTTP Headers in Spring REST Controllers
Java Program to Perform Addition Operation Using Bitwise Operators
Lớp Properties trong java
Spring Data JPA @Modifying Annotation
Java Program to Construct a Random Graph by the Method of Random Edge Selection
So sánh HashMap và Hashtable trong Java
Java Program to Implement Variable length array
A Quick Guide to Spring Cloud Consul
Hướng dẫn Java Design Pattern – Observer
Java Program to Implement the RSA Algorithm
Predicate trong Java 8
Spring Boot - OAuth2 with JWT
Java Program to Implement Stack
The DAO with JPA and Spring
Intro to Spring Boot Starters
Java Program to Construct K-D Tree for 2 Dimensional Data
Java – Random Long, Float, Integer and Double
Java Program to Perform Optimal Paranthesization Using Dynamic Programming
Java Program to Implement Range Tree
Java Program to Implement D-ary-Heap
Hướng dẫn Java Design Pattern – Memento
Login For a Spring Web App – Error Handling and Localization
Hướng dẫn Java Design Pattern – Mediator
Hướng dẫn Java Design Pattern – Iterator