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;
Do you think IIT Guwahati certified course can help you in your career?
No
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
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(); } }
You can also try this code with Online Java Compiler
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.
Refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, JavaScript, System 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.