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?

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

Herewe 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.