在图中使用队列进行拓扑排序

Question

下面是我读的关于队列的拓扑排序算法，我的课本上写的：

void topologicalsort(struct Graph* G){
    struct queue* Q;
    int counter;
    int v,w;
    Q=createqueue();
    counter=0;
    for(v=0;v<G->V;v++){
       if(indegree[v]==0)
          enqueue(Q,v);
       while(!isemptyqueue(Q)){
          v=dequeue(Q);
          topologicalorder[v]=++counter;
          for each w to adjacent to v
             if(--indegree[w]==0){
             enqueue(Q,w);
             }


       }
    } 
}

下图的算法失败：

如果在给定的图中，最初 7 5 3 的度数为零，那么它们将被插入队列中，但是对于任何与 7 5 3 相邻的顶点，我们没有任何度数为 1 的顶点。这意味着 if(--indegree[w]==0) 不会对 7 5 3 成立，因此队列内不会有进一步的排队，因此算法不会处理更多的顶点。 我想知道如果图是 DAG，为什么算法会失败？哪里不对？

我知道我们也可以使用 DFS 实现拓扑排序，但我想按原样实现以下内容：

Answer 1

您的算法实现不正确。这里 while(!isemptyqueue(Q)) 不在 for(v=0;v<G->V;v++) 之下（参见算法中的缩进）。请参阅下文以获得更多说明：

void topologicalsort(struct Graph* G){
    struct queue* Q;
    int counter;
    int v,w;
    Q=createqueue();
    counter=0;
    for(v=0;v<G->V;v++){
       if(indegree[v]==0)
          enqueue(Q,v);
    }

    while(!isemptyqueue(Q)){
         v=dequeue(Q);
         topologicalorder[v]=++counter;
         for each w to adjacent to v {
             if(--indegree[w]==0){
                 enqueue(Q,w);
             }
         }
    }
}

这适用于每个 DAG。

在图中使用队列进行拓扑排序

topological sort using queue in a graph

c

sorting

algorithm

graph-theory

depth-first-search