Topological Sorting using Kahn’s Algorithm in Java

Hello, programmers! In this tutorial, we will learn Java program for Topological sorting using Kahn’s algorithm.

Topological Sorting: The linear ordering of vertices in a Directed Acyclic Graph(DAG) with V vertices and E edges such that every directed edge from vertex u->v, where vertex u comes before v in the order.

In-degree: The number of incoming edges is in-degree for a vertex.

Out-degree: The number of outgoing edges is out-degree for a vertex.

Zero in-degree: The number of incoming edges is zero for a vertex.

Kahn’s Algorithm for Topological Sorting in Java

Let us consider a Directed Acyclic Graph with V vertices and E edges.

Example:

Here, V = 4, E = {{0,3},{2,3},{3,1},{2,1}}

Algorithm:

1. First, find the in-degree of each vertex in the graph.
2. Then, find the edges with zero in-degree. Update them in the queue.
3. If the queue is not empty, then remove a node from the queue and for each outgoing edge of the removed node decrease the in-degree of the destination node by 1.
4.  If the queue is empty then that indicates that there are still some nodes in the graph i.e., the graph contains a cycle and it cannot be topologically sorted.
5. The nodes in the queue represents the topological order of the graph.

import java.util.*; 
public class CodeSpeedy { 
    public static List<Integer> topoSort(List<List<Integer> > u, int v) { 
        int[] indegree = new int[v]; 
        for (int i=0;i<v;i++) { 
            for (int vxt : u.get(i)) { 
                indegree[vxt]++; 
            } 
        } 
        Queue<Integer> q = new LinkedList<>(); 
        for (int i = 0; i < v; i++) { 
            if (indegree[i] == 0) { 
                q.add(i);
            } 
        } 
        List<Integer> result = new ArrayList<>(); 
        while (!q.isEmpty()) { 
            int node = q.poll();
            result.add(node);
            for (int adj : u.get(node)) {
                indegree[adj]--; 
                if (indegree[adj] == 0) q.add(adj); 
            } 
        } 
        if (result.size() != v) { 
            System.out.println("Graph is having cycle!"); 
            return new ArrayList<>();
        } 
        return result;
    }
    public static void main(String[] args) { 
        int n = 4; 
        List<List<Integer> > edges = Arrays.asList( 
            Arrays.asList(0, 3), Arrays.asList(3, 1), 
            Arrays.asList(2, 3), Arrays.asList(2, 1));
        List<List<Integer> > u = new ArrayList<>();
        for (int i = 0; i < n; i++) { 
            u.add(new ArrayList<>()); 
        } 
        for (List<Integer> edge : edges) {
            u.get(edge.get(0)).add(edge.get(1));
        } 
        System.out.print("Topological sorting of the graph: ");
        List<Integer> result = topoSort(u, n);
        for (int vxt : result) { 
            System.out.print(" "+vxt);
        }
    }
 }

Output:

Topological sorting of the graph: 0 2 3 1