使用 Kahn 算法的拓扑排序

Question

我想知道，下面这部分代码是什么意思，我了解整个功能，但 for loop at the end 让我感到困惑，无法理解。那么请告诉我它在那里做什么？

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); 
    } 
}

这 link 到整个代码 https://ide.geeksforgeeks.org/PSNw3VplJL

Answer 1

Kahn 算法（与 BFS 无关）：

找到入度为 0 的所有顶点并将它们放入队列中（q 在您的代码中）。
从队列中选择一个顶点，将其输出，并将其从图中删除。
删除顶点将减少其所有邻居的入度。其中一些可能达到入度 0 - 将这些放入队列中。
回到 2 直到你没有顶点。

最后一个 for 循环执行步骤 (3)。

使用 Kahn 算法的拓扑排序

Topological Sorting using Kahn's Algorithm

c++

graph

data-structures