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.

```
/**
```

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

« Prev - Java Program to Implement Gaussian Elimination Algorithm

» Next - Java Program to Solve the Knapsack Problem

Related Posts:

Recommended Articles: