1.
Introduction
2.
What is Kahn's Algorithm?
3.
Explanation for the output:
4.
Algorithm:
5.
How to Get In-degree for each vertex of Graph?
5.1.
1. Take an in-degree array which will keep track of  indegree-of the vertex,Traverse the edge array of the graph and increase the destination node value with the one.
5.2.
2. Traverse every node of the graph and than increment it as , How many node are connected to it and the connection is inward;
6.
Code for the Algorithm:
6.1.
java
6.2.
What is the Complexity for the Kahnâ€™s Algorithm?
7.
Application of Kahnâ€™s algorithm
8.
8.1.
Is Kahn algorithm a BFS?
8.2.
What is the complexity of Khan's algorithm?
8.3.
Who invented Kahn's algorithm?
8.4.
How do you detect A cycle using Kahn's algorithm?
9.
Conclusion
Last Updated: Mar 27, 2024

# Kahn's Algorithm for Topological Sorting

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

Topological sorting is Done for Directed Acyclic Graph(DAG).In which Linearing ordering of vertices is achieved where for every edge that is directed (name-UV).

Note, Here you are, the starting vertex, and v is the ending vertex.

Topological sorting handling Khanâ€™s algorithm.

## What is Kahn's Algorithm?

It is a sorting Algorithm used for sorting Topological Directed Acyclic Graph(DAG). This algorithm is applicable only in the case of a Directed Acyclic Graph(DAG).

The first vertex in the Topological Sorting of graphs is decided because the node has the In-Degree zero(i.e. the node has zero incoming nodes). One important thing that must be kept in mind is that topological sorting can have more than one sorting. For example, the below graph can have two sorting i.e

• 5 ,4 ,2 ,3 ,1 ,0,,
• 4 ,5 ,2 ,0 ,3 ,1
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Explanation for the output:

Topical Sorting for the Directed acyclic graph is done so that every edge begins with u (vertex ) and ends with v(vertex).In the above, Image 5 has no Incoming edge. The same scenario is with vertex 4, Whereas 0, 1 has an incoming edge only no outgoing edge.  in  0â€ť have the incoming edges from 5,4, so one comes at last, so the order is

5,4,2,3,1,0;

Note:

A Directed Acyclic Graph has a minimum of one vertex Where Indegene Zero and OutDegree is Zero.

## Algorithm:

• Step1: Compute the Indegree of all the vertices of the Graph and Initialize the variable count with zero(It maintains the Visited node count)

• Step 2: All the nodes with the in-degree must have zero pick them and put them in a Queue

• Step 3: Pick the node from the Queue mark it visited then, increment the count value and Decrement the Indegree value for all the nodes that are edges from the given node

• Step 4: Keep Doing step 3 until the Queue is Empty

• Step 5: Now compare the count value with the no of nodes of the graph,in-degree, and if they are not equal, then the Topological sort is not possible for the Graph.

## How to Get In-degree for each vertex of Graph?

We deal with two major methods to find the in-degree of the vertex of the graph they are:

### 1. Take an in-degree array which will keep track of  indegree-of the vertex,Traverse the edge array of the graph and increase the destination node value with the one.

``````//initialization for each node
for each node in Nodes
indegree[node] = 0;
//increment if the indegree for the node if it is the destination node
for each edge(source, destination) in Edges
indegree[destination]++;``````

Time Complexity: Since we are travelling the node first and then we are travelling the edges,, o the time complexity is o(V+E);

### 2. Traverse every node of the graph and than increment it as , How many node are connected to it and the connection is inward;

``````//traversing the every node of graph
for each nodes in Node
//finding no of incoming node to it
If (list[nodes].size()!=0) then
for each destination in lists
indegree[destination]++;``````

Time Complexity: Here we have, two loops in the two the outer loops would run (no of vertices time i.e. V), the inner loop run (no of edges time i.e. E) so the time complexity is o(V+E);

## Code for the Algorithm:

• java

### java

``import java.util.*;// Class to represent a graphclass Graph {    int V;    List<Integer> adj[];    public Graph(int V) {        this.V = V;        adj = new ArrayList[V];        for (int i = 0; i < V; i++)            adj[i] = new ArrayList<Integer>();    }    public void addEdge(int u, int v) {        adj[u].add(v);    }    public void topologicalSort() {        int in_degree[] = new int[V];        for (int i = 0; i < V; i++) {            ArrayList<Integer> temp = (ArrayList<Integer>) adj[i];            for (int node : temp) {                in_degree[node]++;            }        }        Queue<Integer> q = new LinkedList<Integer>();        for (int i = 0; i < V; i++) {            if (in_degree[i] == 0) {                q.add(i);            }        }        int cnt = 0;        Vector<Integer> topOrder = new Vector<Integer>();        boolean[] visited = new boolean[V];        while (!q.isEmpty()) {            int u = q.poll();            topOrder.add(u);            visited[u] = true;            for (int node : adj[u]) {                if (!visited[node]) {                    if (--in_degree[node] == 0) {                        q.add(node);                    }                } else {                    System.out.println("Cycle detected in the graph");                    return;                }            }            cnt++;        }        if (cnt != V) {            System.out.println("Cycle is present in the graph");            return;        }        for (int i : topOrder) {            System.out.print(i + " ");        }    }}public class Main {    public static void main(String args[]) {        Graph codingninjas = new Graph(6);        codingninjas.addEdge(5, 2);        codingninjas.addEdge(5, 0);        codingninjas.addEdge(4, 0);        codingninjas.addEdge(4, 1);        codingninjas.addEdge(2, 3);        codingninjas.addEdge(3, 1);        System.out.println("Topological Sort function will run now");        codingninjas.topologicalSort();    }}``

Output:

### What is the Complexity for the Kahnâ€™s Algorithm?

Time Complexity

Here we are travelling with the vertices and edges, and the outer loop is crossing, travelling the no of vertices time, so, i.e. V and the inner circle is traversing the no of Edges time, so Time Complexity is :

O(V+E);

Space Complexity

Here we need an additional Queue for Storing all the vertices with an out-degree zero, so the Space complexity is:

O(V).

## Application of Kahnâ€™s algorithm

Here are some key applications of Kahn's algorithm:

• Task Scheduling: Determining the order in which tasks or jobs should be executed to meet dependencies or constraints

• Course Scheduling: Scheduling courses in academic institutions while considering prerequisites

• Workflow Management: Designing and executing workflows in data processing or automation systems

• Network Routing: Finding the optimal path or order for data or signal transmission in networks

• Optimization Problems: Solving optimization problems that involve ordering or sequencing constraints

• Resource Allocation: Managing resource allocation in scenarios with interdependent tasks or processes

### Is Kahn algorithm a BFS?

Kahn's algorithm is not a breadth-first search (BFS) algorithm, although it is often used in conjunction with BFS for topological sorting of directed acyclic graphs (DAGs).

### What is the complexity of Khan's algorithm?

The complexity of Kahn's algorithm for topological sorting is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the directed graph.

### Who invented Kahn's algorithm?

Kahn's algorithm was developed by Arthur Kahn.

### How do you detect A cycle using Kahn's algorithm?

To detect a cycle using Kahn's algorithm, count the number of nodes processed. If, at the end of the algorithm, some nodes remain unprocessed, a cycle is present. In a valid directed acyclic graph (DAG), Kahn's algorithm should process all nodes; if it doesn't, a cycle exists.

## Conclusion

The blog explained Topological sorting and how topological sorting is achieved using Kahnâ€™s algorithm.