Topological Sorting using Kahn's Algorithm

Question

I wanted to know ,what does the following part of code mean , I understood the whole function but the for loop at the end is making me confused and not able to understand. So please tell me what it is doing there?

void topologicalSort(vector<int> adj[], int V) 
{ 
    vector<int> in_degree(V, 0); 
  
    for (int u = 0; u < V; u++) { 
        for (int x:adj[u]) 
            in_degree[x]++; 
    } 
  
    queue<int> q; 
    for (int i = 0; i < V; i++) 
        if (in_degree[i] == 0) 
            q.push(i); 

  
    while (!q.empty()) { 
        int u = q.front(); 
        q.pop(); 
        cout<<u<<" "; 
  
        for (int x: adj[u]) 
            if (--in_degree[x] == 0) 
                q.push(x); 
    } 
}

This the link to whole code https://ide.geeksforgeeks.org/PSNw3VplJL

Matt Timmermans · Accepted Answer · 2022-01-11 03:08:06Z

1

Kahn's algoritm (which has nothing to do with BFS):

Find all the vertexes with in-degree 0 and put them in a queue (q in your code).
Pick a vertex from the queue, output it, and delete it from the graph.
Deleting the vertex will reduce the in-degree of all its neighbors. Some of these could reach in-degree 0 -- put those ones in the queue.
Go back to 2 until you're out of vertexes.

That last for loop does step (3).

answered Jan 11, 2022 at 3:08

Matt Timmermans

60.8k3 gold badges57 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Topological Sorting using Kahn's Algorithm

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related