c++ - 最小可用顶点优先的拓扑排序

Question

我正在尝试解决基于 TopSort 的问题。由于将有许多有效的拓扑排序顺序，我需要输出字典序最小的一个，即首先输出最小编号的可用顶点。

我会说明我采用的方法，然后贴出代码。我维护了一个数组，其中包含图中每个节点的入边数。还存在邻接矩阵。我有一个 bool 数组“已访问”，它保留了访问节点的计数，以及一个最小优先级队列，用于在那一刻弹出最小的可用顶点。这是我的代码:

void dfs(int u){

    visited[u] = true;
    cout<<u<<" ";

    list<int>::iterator i;
    for(i = adj[u].begin(); i != adj[u].end(); ++i){

        if(!visited[*i]){

            inedge[*i]--;
            if(!inedge[*i]){
                pq.push(*i);
            }

            if(!pq.empty()){
                int temp = pq.top();
                pq.pop();
                dfs(temp);
            }
        }
    }
}

现在，在第一次调用此函数时，优先级队列仅包含 inedge[i]=0(入边数为零)的那些节点。我从那个优先级队列 u = pq.top() 中弹出最小节点，然后调用 dfs(u)。

但是我的代码给出了错误的输出。如果我在这里使用的逻辑是错误的，有人可以帮助我吗？

我的输入由 N 个不完整的序列组成(N 个中的每个序列都缺少数字)。输入:

2
1 3
2 3 4

输出:

1 2 3 4

这是正确的预期输出，我的代码确实生成了它。但是对于 this 中给出的输入图片输入:

6
7 8 9
7 11 9
5 11 2
3 8 9
11 10
3 10

预期输出是:

3 5 7 8 11 2 9 10

我的代码输出:

3 5 7 8 11 9 2 10

我的代码也为其他一些测试用例输出了错误的结果，但我不知道如何解决这个问题。

Answer 1

问题似乎是 pq.top 在检查当前节点的所有出边之前被调用。

考虑下图:节点:A、B、C；边 A->B，A-C。让 C 具有较小的优先级值，即它应该排在第一位。在 dfs(A) 期间，您在 C 之前检查 B。由于它立即再次从队列中取出，因此首先处理 B(但不应该)。因此，在再次查询队列之前插入所有相邻节点。