# 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! 