Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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.

Kahn's Algorithm

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 graph
class 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

Frequently Asked Questions

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.

Recommended Reads:-

Recommended Problems

Do check out The Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Previous article
Check If Cells Numbered 1 to K In A Grid Can Be Connected After The Removal Of At most One Blocked Cell
Next article
Optimal read list for given number of days
Live masterclass