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 Shell Sort
Java Program to Implement First Fit Decreasing for 1-D Objects and M Bins
Tránh lỗi NullPointerException trong Java như thế nào?
Java Streams vs Vavr Streams
ExecutorService – Waiting for Threads to Finish
Weak References in Java
Multi Dimensional ArrayList in Java
Wrapper Classes in Java
Creating a Generic Array in Java
Java Program to Represent Linear Equations in Matrix Form
Spring Data JPA Delete and Relationships
Java Program to Implement Bresenham Line Algorithm
Comparing getPath(), getAbsolutePath(), and getCanonicalPath() in Java
Java – Reader to InputStream
Java – String to Reader
Simultaneous Spring WebClient Calls
Lớp TreeMap trong Java
Biến trong java
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Hướng dẫn Java Design Pattern – Template Method
A Guide to Apache Commons Collections CollectionUtils
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Spring Boot - Flyway Database
Java Program to Implement Borwein Algorithm
@Order in Spring
Java Program to Implement Strassen Algorithm
Java Program to Implement Extended Euclid Algorithm
Summing Numbers with Java Streams
Java Program to Implement Triply Linked List
Java Program to Find SSSP (Single Source Shortest Path) in DAG (Directed Acyclic Graphs)
Check If a File or Directory Exists in Java
Registration with Spring Security – Password Encoding