This is a Java Program to Implement Kosaraju Algorithm. Kosaraju’s algorithm is a linear time algorithm to find the strongly connected components of a directed graph.
Here is the source code of the Java Program to Implement Kosaraju Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement Kosaraju Algorithm **/ import java.util.*; /** class Kosaraju **/ public class Kosaraju { /** DFS function **/ public void DFS(List<Integer>[] graph, int v, boolean[] visited, List<Integer> comp) { visited[v] = true; for (int i = 0; i < graph[v].size(); i++) if (!visited[graph[v].get(i)]) DFS(graph, graph[v].get(i), visited, comp); comp.add(v); } /** function fill order **/ public List<Integer> fillOrder(List<Integer>[] graph, boolean[] visited) { int V = graph.length; List<Integer> order = new ArrayList<Integer>(); for (int i = 0; i < V; i++) if (!visited[i]) DFS(graph, i, visited, order); return order; } /** function to get transpose of graph **/ public List<Integer>[] getTranspose(List<Integer>[] graph) { int V = graph.length; List<Integer>[] g = new List[V]; for (int i = 0; i < V; i++) g[i] = new ArrayList<Integer>(); for (int v = 0; v < V; v++) for (int i = 0; i < graph[v].size(); i++) g[graph[v].get(i)].add(v); return g; } /** function to get all SCC **/ public List<List<Integer>> getSCComponents(List<Integer>[] graph) { int V = graph.length; boolean[] visited = new boolean[V]; List<Integer> order = fillOrder(graph, visited); /** get transpose of the graph **/ List<Integer>[] reverseGraph = getTranspose(graph); /** clear visited array **/ visited = new boolean[V]; /** reverse order or alternatively use a stack for order **/ Collections.reverse(order); /** get all scc **/ List<List<Integer>> SCComp = new ArrayList<>(); for (int i = 0; i < order.size(); i++) { /** if stack is used for order pop out elements **/ int v = order.get(i); if (!visited[v]) { List<Integer> comp = new ArrayList<>(); DFS(reverseGraph, v, visited, comp); SCComp.add(comp); } } return SCComp; } /** main **/ public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Kosaraju algorithm Test\n"); Kosaraju k = new Kosaraju(); System.out.println("Enter number of Vertices"); /** number of vertices **/ int V = scan.nextInt(); List<Integer>[] g = new List[V]; for (int i = 0; i < V; i++) g[i] = new ArrayList<Integer>(); System.out.println("\nEnter number of edges"); int E = scan.nextInt(); /** all edges **/ System.out.println("Enter "+ E +" x, y coordinates"); for (int i = 0; i < E; i++) { int x = scan.nextInt(); int y = scan.nextInt(); /** add edge **/ g[x].add(y); } System.out.println("\nSCC : "); /** print all strongly connected components **/ List<List<Integer>> scComponents = k.getSCComponents(g); System.out.println(scComponents); } }
Kosaraju algorithm Test Enter number of Vertices 8 Enter number of edges 14 Enter 14 x, y coordinates 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 SCC : [[1, 4, 0], [7, 3, 2], [5, 6]]
Related posts:
Java Program to Implement Extended Euclid Algorithm
The Thread.join() Method in Java
Java Program to Compute Determinant of a Matrix
Tính kế thừa (Inheritance) trong java
Java – Random Long, Float, Integer and Double
Java – Reader to Byte Array
Java Program to Check for balanced parenthesis by using Stacks
Spring NoSuchBeanDefinitionException
Spring Cloud AWS – RDS
Enum trong java
JPA/Hibernate Persistence Context
Java Program to Implement a Binary Search Algorithm for a Specific Search Sequence
Spring Boot - Introduction
Convert String to int or Integer in Java
Java Program to Search Number Using Divide and Conquer with the Aid of Fibonacci Numbers
How to Return 404 with Spring WebFlux
Get and Post Lists of Objects with RestTemplate
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Java Program to Show the Duality Transformation of Line and Point
Java Program to Implement String Matching Using Vectors
Java Program to Implement Hash Tables chaining with Singly Linked Lists
How to Add a Single Element to a Stream
Converting Between an Array and a Set in Java
Introduction to Using FreeMarker in Spring MVC
Java – String to Reader
String Initialization in Java
Java Program to Implement EnumMap API
Guava Collections Cookbook
Java Program to Compute DFT Coefficients Directly
Spring Boot - Rest Template
Java Program to Implement ScapeGoat Tree
Java Program to Repeatedly Search the Same Text (such as Bible by building a Data Structure)