This Java program, displays the Strong Connected Components of graph.A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular , this means paths in each direction; a path from a to b and also a path from b to a.
Here is the source code of the Java program to display the Strong Connected Components of a graph. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.HashMap; import java.util.InputMismatchException; import java.util.Map; import java.util.Scanner; import java.util.Stack; public class StrongConnectedComponents { private int leader = 0; private int[] leader_node; private int explore[]; private int finishing_time_of_node[]; private int finishing_time = 1; private int number_of_nodes; private Stack<Integer> stack; private Map<Integer, Integer> finishing_time_map; public StrongConnectedComponents(int number_of_nodes) { this.number_of_nodes = number_of_nodes; leader_node = new int[number_of_nodes + 1]; explore = new int[number_of_nodes + 1]; finishing_time_of_node = new int[number_of_nodes + 1]; stack = new Stack<Integer>(); finishing_time_map = new HashMap<Integer, Integer>(); } public void strongConnectedComponent(int adjacency_matrix[][]) { for (int i = number_of_nodes; i > 0; i--) { if (explore[i] == 0) { dfs_1(adjacency_matrix, i); } } int rev_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; for (int i = 1; i <= number_of_nodes; i++) { for (int j = 1; j <= number_of_nodes; j++) { if (adjacency_matrix[i][j] == 1) rev_matrix[finishing_time_of_node[j]][finishing_time_of_node[i]] = adjacency_matrix[i][j]; } } for (int i = 1; i <= number_of_nodes; i++) { explore[i] = 0; leader_node[i] = 0; } for (int i = number_of_nodes; i > 0; i--) { if (explore[i] == 0) { leader = i; dfs_2(rev_matrix, i); } } } public void dfs_1(int adjacency_matrix[][], int source) { explore = 1; stack.push(source); int i = 1; int element = source; while (!stack.isEmpty()) { element = stack.peek(); i = 1; while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && explore[i] == 0) { stack.push(i); explore[i] = 1; element = i; i = 1; continue; } i++; } int poped = stack.pop(); int time = finishing_time++; finishing_time_of_node[poped] = time; finishing_time_map.put(time, poped); } } public void dfs_2(int rev_matrix[][], int source) { explore = 1; leader_node[finishing_time_map.get(source)] = leader; stack.push(source); int i = 1; int element = source; while (!stack.isEmpty()) { element = stack.peek(); i = 1; while (i <= number_of_nodes) { if (rev_matrix[element][i] == 1 && explore[i] == 0) { if (leader_node[finishing_time_map.get(i)] == 0) leader_node[finishing_time_map.get(i)] = leader; stack.push(i); explore[i] = 1; element = i; i = 1; continue; } i++; } stack.pop(); } } public static void main(String... arg) { int number_of_nodes; Scanner scanner = null; try { System.out.println("Enter the number of nodes in the graph"); scanner = new Scanner(System.in); number_of_nodes = scanner.nextInt(); int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; System.out.println("Enter the adjacency matrix"); for (int i = 1; i <= number_of_nodes; i++) for (int j = 1; j <= number_of_nodes; j++) adjacency_matrix[i][j] = scanner.nextInt(); StrongConnectedComponents strong = new StrongConnectedComponents(number_of_nodes); strong.strongConnectedComponent(adjacency_matrix); System.out.println("The Strong Connected Components are"); for (int i = 1; i < strong.leader_node.length; i++) { System.out.println( "Node " + i+ "belongs to SCC" + strong.finishing_time_map.get(strong.leader_node[i])); } } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input Format"); } } }
$javac StrongConnectedComponents.java $java StrongConnectedComponenets Enter the number of nodes in the graph 8 Enter the adjacency matrix 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 The Strong Connected Components are Node 1 belongs to SCC 2 Node 2 belongs to SCC 2 Node 3 belongs to SCC 8 Node 4 belongs to SCC 4 Node 5 belongs to SCC 8 Node 6 belongs to SCC 2 Node 7 belongs to SCC 2 Node 8 belongs to SCC 8
Related posts:
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Java Program to Implement Splay Tree
Spring Boot - Internationalization
Java program to Implement Tree Set
Java Program to Perform Insertion in a BST
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm
Call Methods at Runtime Using Java Reflection
A Custom Media Type for a Spring REST API
Constructor Dependency Injection in Spring
CyclicBarrier in Java
Hướng dẫn sử dụng Java Generics
Cơ chế Upcasting và Downcasting trong java
Jackson – Unmarshall to Collection/Array
Java Byte Array to InputStream
Java 8 and Infinite Streams
Hướng dẫn Java Design Pattern – Memento
Giới thiệu Google Guice – Injection, Scope
Spring Boot: Customize Whitelabel Error Page
Java Program to Find the Edge Connectivity of a Graph
Java Program to Convert a Decimal Number to Binary Number using Stacks
Java Program to Implement Leftist Heap
Understanding Memory Leaks in Java
Java – InputStream to Reader
Read an Outlook MSG file
Spring Data Reactive Repositories with MongoDB
Java Program to Implement Queue using Two Stacks
Jackson Date
Spring Boot - Service Components
Deploy a Spring Boot App to Azure
Java Program to Implement ConcurrentSkipListMap API
Java Program to Implement Find all Back Edges in a Graph
Java Program to Implement Park-Miller Random Number Generation Algorithm