关于求图的拓扑排序问题之bfs

Question

关于求图的拓扑排序问题之bfs

```c++
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idex,n,m,q[N],d[N];
void add(int a,int b){
    e[idex]=b;
    ne[idex]=h[a];
    h[a]=idex;
    idex++;
}
bool topsort(){
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++){
        if(!d[i]) q[++tt]=i;
    }
    while(hh<=tt){
        //首先拿出队头元素
        int t=q[hh++];
        //进行拓展
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            
            if(--d[j]==0) q[++tt]=j;
        } 
    }
    //检查进队了多少个元素
    return tt==n-1; 
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    while(m--){
        int x,y;
        cin>>x>>y;
        add(x,y);
        d[y]++;
    }
    if(topsort()){
        for(int i=0;i<n;i++)  cout<<q[i]<<" ";
        cout<<endl;
    }
    else printf("-1\n");
    return 0;
}

为什么在上述代码之中将

for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            
            if(--d[j]==0) q[++tt]=j;
        } 

改成
```c++
for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(!d[j]) d[j]--;
            if(d[j]==0) q[++tt]=j;
        } 

之后运行结果是错误的呢

Answer 1

引自免费微信小程序：皆我百晓生

在原始代码中，if(--d[j]==0) 的写法实际上是在递减 d[j] 的同时检查其是否为零。这样做的问题是，在某些情况下可能会导致节点被错误地添加到拓扑排序序列中，尤其是在存在环路的情况下。

当我们将这段代码修改为：

for(int i=h[t];i!=-1;i=ne[i]){
    int j=e[i];
    if(!d[j]) d[j]--;
    if(d[j]==0) q[++tt]=j;
}

这里，我们先检查 d[j] 是否为零，然后再递减它。这个改动使得我们只会在 d[j] 非零时才递减它。这样做的好处是可以确保在处理有向图中的环路时，不会错误地添加环内的节点到拓扑排序序列中，因为环内所有节点的入度永远不会变为零。

然而，这个改动并不能解决所有情况下的拓扑排序问题，尤其是对于存在环路的情况。如果图中有环，那么在任何情况下，环内的节点都无法进行拓扑排序，因为它们的入度永远不可能降为零。因此，我们需要一个额外的方法来检测环路并返回错误信息。

以下是修复后的代码，包括了一个简单的环路检测方法：

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idex,n,m,q[N],d[N],vis[N];

// 新增函数用于检测环路
bool hasCycleUtil(int node, bool visited[], int parent){
    visited[node] = true;
    
    for(int i = h[node]; i != -1; i = ne[i]){
        int adj = e[i];
        
        if(!visited[adj]){
            if(hasCycleUtil(adj, visited, node)) return true;
        }
        else if(parent != adj) // 如果找到回边，则表示有环
            return true;
    }
    return false;
}

bool hasCycle(){
    bool visited[N] = {false};
    for(int i = 1; i <= n; ++i){
        if(!visited[i] && hasCycleUtil(i, visited, -1))
            return true;
    }
    return false;
}

bool topsort(){
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++){
        if(!d[i]) q[++tt]=i;
    }
    while(hh<=tt){
        // 首先拿出队头元素
        int t=q[hh++];
        // 进行拓展
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            
            if(!d[j]) d[j]--;
            if(d[j]==0) q[++tt]=j;
        } 
    }
    // 检查进队了多少个元素，并且检测是否有环
    return tt==n-1 && !hasCycle();
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    while(m--){
        int x,y;
        cin>>x>>y;
        add(x,y);
        d[y]++;
    }
    if(topsort()){
        for(int i=0;i<n;i++)  cout<<q[i]<<" ";
        cout<<endl;
    }
    else printf("-1\n");
    return 0;
}

在这个版本中，我增加了 hasCycleUtil() 函数，这是一个深度优先搜索（DFS）辅助函数，用于检测图中是否存在环。另外，我还添加了 hasCycle() 函数，它会遍历每个未访问过的节点，调用 hasCycleUtil() 来检测环路。如果检测到环路，hasCycle() 将返回 true。在 topsort() 函数中，我们在计算拓扑排序后检查是否有环，如果有则返回 false。这样，即使在存在环路的情况下，程序也能正确地返回 -1。