Java Program to Implement Kosaraju Algorithm

«
»
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.

  1. /**
  2.  ** Java Program to Implement Kosaraju Algorithm
  3.  **/
  4.  
  5. import java.util.*;
  6.  
  7. /** class Kosaraju **/
  8. public class Kosaraju
  9. {
  10.     /** DFS function **/
  11.     public void DFS(List<Integer>[] graph, int v, boolean[] visited, List<Integer> comp) 
  12.     {
  13.         visited[v] = true;
  14.         for (int i = 0; i < graph[v].size(); i++)
  15.             if (!visited[graph[v].get(i)])
  16.                 DFS(graph, graph[v].get(i), visited, comp);
  17.         comp.add(v);
  18.     }
  19.     /** function fill order **/
  20.     public List<Integer> fillOrder(List<Integer>[] graph, boolean[] visited) 
  21.     {        
  22.         int V = graph.length;
  23.         List<Integer> order = new ArrayList<Integer>();
  24.  
  25.         for (int i = 0; i < V; i++)
  26.             if (!visited[i])
  27.                 DFS(graph, i, visited, order);
  28.         return order;
  29.     }
  30.     /** function to get transpose of graph **/
  31.     public List<Integer>[] getTranspose(List<Integer>[] graph)
  32.     {
  33.         int V = graph.length;
  34.         List<Integer>[] g = new List[V];
  35.         for (int i = 0; i < V; i++)
  36.             g[i] = new ArrayList<Integer>();
  37.         for (int v = 0; v < V; v++)
  38.             for (int i = 0; i < graph[v].size(); i++)
  39.                 g[graph[v].get(i)].add(v);
  40.         return g;
  41.     }
  42.     /** function to get all SCC **/
  43.     public List<List<Integer>> getSCComponents(List<Integer>[] graph)
  44.     {
  45.         int V = graph.length;
  46.         boolean[] visited = new boolean[V];
  47.         List<Integer> order = fillOrder(graph, visited);       
  48.         /** get transpose of the graph **/
  49.         List<Integer>[] reverseGraph = getTranspose(graph);        
  50.         /** clear visited array **/
  51.         visited = new boolean[V];
  52.         /** reverse order or alternatively use a stack for order **/
  53.         Collections.reverse(order);
  54.  
  55.         /** get all scc **/
  56.         List<List<Integer>> SCComp = new ArrayList<>();
  57.         for (int i = 0; i < order.size(); i++)
  58.         {
  59.             /** if stack is used for order pop out elements **/
  60.             int v = order.get(i);
  61.             if (!visited[v]) 
  62.             {
  63.                 List<Integer> comp = new ArrayList<>();
  64.                 DFS(reverseGraph, v, visited, comp);
  65.                 SCComp.add(comp);
  66.             }
  67.         }
  68.         return SCComp;
  69.     }
  70.     /** main **/
  71.     public static void main(String[] args)
  72.     {
  73.         Scanner scan = new Scanner(System.in);
  74.         System.out.println("Kosaraju algorithm Test\n");
  75.         Kosaraju k = new Kosaraju();
  76.  
  77.         System.out.println("Enter number of Vertices");
  78.         /** number of vertices **/
  79.         int V = scan.nextInt();
  80.         List<Integer>[] g = new List[V];
  81.         for (int i = 0; i < V; i++)
  82.             g[i] = new ArrayList<Integer>();
  83.  
  84.         System.out.println("\nEnter number of edges");
  85.         int E = scan.nextInt();
  86.         /** all edges **/
  87.         System.out.println("Enter "+ E +" x, y coordinates");
  88.         for (int i = 0; i < E; i++)
  89.         {
  90.             int x = scan.nextInt();
  91.             int y = scan.nextInt();
  92.             /** add edge **/
  93.             g[x].add(y);
  94.         }
  95.         System.out.println("\nSCC : ");
  96.         /** print all strongly connected components **/
  97.         List<List<Integer>> scComponents = k.getSCComponents(g);
  98.         System.out.println(scComponents);    
  99.     }    
  100. }

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]]

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.