在图中检测环路（使用三色机制）

Question

我知道如何使用三种颜色（黑、白和灰）机制检测图中的循环。不了解此方法的人，请按照以下步骤操作： http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/ 简单来说，白色节点是未发现的节点，灰色节点是正在处理的节点，黑色节点是已发现的节点。

几天前，一位高级工程师问我为什么需要恰好三种颜色来做这个。我们不能只用黑色和白色吗？为什么真的需要灰色节点？我很抱歉无法回答他的问题。你们中的任何人可以告诉我他是否在问一个有效的问题或者只是在测试我吗？

- Hemant Bhargava

Answer 1

不，他并没有在测试你。在仅使用两种颜色的情况下可以检测图中的循环，但在这种情况下，图必须是无向的。

详细说明：

我想强调的是，根据边缘方向的方式，图形有两种类型，当我们有一个图形时，在两个顶点之间所有边都向前和向后移动时，图形的类型称为无向图。

以下图片是一个有向图。

这两者在理论上的区别是，在无向图中我们不需要绘制边的方向。当我们提到在无向图中节点A和B之间存在一条边时，自动意味着反向边也存在。为什么我们要谈论反向边呢？因为在计算机程序中，边的表示方式有所不同，我们只指定有向边。例如，在邻接表中，只有当从A到B存在一条边时，节点B才会出现在节点A的邻接表中。因此，在这种表示中，如果我们需要显示从B到A也存在一条边，则还需要将节点A添加到节点B的邻接表中。

同样，在基于邻接矩阵的表示中，矩阵关于其主对角线（从左上角开始的对角线）对称，以显示从A到B的每条边都存在一条从B到A的边。

因此，为了实现任何无向图，我们需要执行以下操作：

当你用这个方法替换无向图的所有边之后，你就可以在计算机表达中看到实际的图像。

现在假设你已经有了一个图。你要问，是哪一个？

一个无向图

我将参考此处发布的第一张图片。并且假设使用邻接表表示法来表示图。

它会是什么样子？看这里：

A：B -> D -> E -> NULL
B：A -> D -> E -> NULL
C：D -> NULL
D：A -> B -> C -> NULL
E：A -> B -> NULL

目标是设计一些策略来检查是否存在循环。

现在假设这些节点代表城市中的一些商店，边缘是道路，所以如果你看到从节点A到B的道路，那么自动地存在一条从B到A的道路，因为图是无向的。从邻接表中也可以看出同样的信息。

为了检测无向图中的循环，我们将按照以下步骤进行，这是一个典型程序所遵循的方式。然后你将看到我给出的陈述是有效的。让我们开始吧。

我们从节点A开始，想要遍历整个图，遍历意味着你想要访问所有商店。现在为了真正跟踪你访问过的商店，当你离开它们时，你会给它们染色，因此你站在节点A上，现在有许多道路从节点A出现，你可以走其中的一条去其他地方。所有这些选项都在A的邻接表中。

假设你选择了一条通往节点B的路，并沿着它前进，离开A之前给它染色。现在站在B上，你首先看到的是，这个节点被染色了吗？你没有看到任何颜色!! 然后你知道你以前没有访问过这个节点。再次想做同样的事情，所以你查看B的邻接表以选择下一条路，你看到一条通往A的路，你再次沿着那条路走到达A，离开时把B染色。但是，当你到达节点A时，你发现它也被染色了，这意味着你以前访问过这家商店，但是你意识到因为图是无向的，所以从B到达A并不是一个问题，因为边是双向的，所以你回溯。

为了避免再次出现这种情况，您可以使用父数组，其中par[i] = j，如果您从j发现i。现在，您已经消除了再次访问父级的陷阱。现在您选择从B到E的下一个路线，您去那里，将B着色，并设置par[E] = B。当您到达E时，您想再次执行相同的操作。但是这一次，您看到了通往A的道路，首先要检查A是否是您的父节点？因为您不希望再次访问您的父节点，因为您已经从那里来过。

答案是否定的。所以您去了A，但是当您到达A时，您注意到该节点已经着色。如果这是真的，那么这意味着您已经访问了A，这意味着存在一条路径从A结束于A，因此存在一个循环。

那么告诉我我们使用了多少种颜色？仅有两种，一种是初始颜色，另一种是访问节点后的颜色。

你可能会说我在这个特定的示例中展示了它，因此该过程不一定总是有效，但请尝试理解我所描述的情况，并试着让自己相信，如果你从一个节点开始，按照一组路径走到某个地方，看到该节点已被涂色，那么就意味着你已经访问过该节点，由于你避免访问该节点的父节点，因此你能看到一个节点被涂色的唯一方式是因为存在某个循环。

我将让你自己意识到为什么这种方法在有向图中不起作用，以及双向边的机制在这里扮演的角色。

- Prem KTiw

---

请详细说明。谢谢。 - Hemant Bhargava

@Prem KTiw 您的答案不正确。黑色可以被消除，但白色和灰色是必需的。仅消除黑色将使算法变慢，这就是全部。 - curiousengineer

Answer 2

这里是你所需的所有解释。

https://cs.stackexchange.com/questions/9676/the-purpose-of-grey-node-in-graph-depth-first-search

基本上，白色节点在第一次访问后会变成灰色，但只有在所有邻居都变成黑色或没有未访问的邻居时，灰色节点才会变成黑色。

在有向图中，只有在所有后代被访问之前再次看到一个节点时才存在循环。换句话说，如果一个节点有一个灰色的邻居，则存在一个循环（而不是当邻居为黑色时）。灰色节点意味着我们正在探索其后代 - 如果这样的后代与此灰色节点有边，则存在一个循环。因此，在有向图中检测循环，需要使用3种颜色。

现在应该很清楚，两种颜色是不够的。

- Coderslang Master

---

太棒了！谢谢。这正是我需要的。 - Hemant Bhargava

@Default71721 这仅适用于有向图，并且问题没有针对图的性质提出任何具体要求。如果图是无向的，则只需要两种颜色。请阅读我的答案以获取更多信息。 - Prem KTiw

Answer 3

对于无向图，只需要两种颜色即可。但是对于有向图，我们需要三种颜色。为什么有向图需要三种颜色呢？从以下示例中可以清楚地看到原因：当我们访问节点D及其所有邻居时，它变成黑色。当我们从某个先前的节点A使用另一条路径再次到达此节点时，我们意识到该节点已经被访问过。由于该节点的颜色是黑色，这意味着在该节点我们已经探索了所有邻居并且没有从D到A的路径，因此我们已经回溯。因此，我们得出结论，在A和D之间没有循环。

考虑有向图中的另一种情况，如果我们仅使用两种颜色，则第二次从A到达D时，我们将得到节点D的灰色，这意味着在第一轮中已经访问过它，因此我们得出结论认为存在循环，而实际上并非如此。这就是第三种颜色的重要性。

- Satyam Gupta

Answer 4

对于有向图来说，只需要两种颜色即可。假设我们一直使用的白色、灰色和黑色的约定是正确的，那么使用黑色的唯一原因是为了优化算法。如果我们不使用灰色，就会重复访问一个尚未完全处理的节点，并且无法检测到循环。但是，如果我们不维护黑色节点列表，算法将只会多次或甚至多次遍历节点和其邻居，但只要白色和灰色节点以相同的方式使用，它仍然可以正常工作。

- curiousengineer

Answer 5

#include<bits/stdc++.h>
using namespace std;
list<int>adj[10000];
int flag =0;
void dfs(int s , bool visited[] , char color[]){
    visited[s] = true;
    color[s] = 'g';
    std::list<int>::iterator ii;
    for(ii=adj[s].begin() ; ii!=adj[s].end(); ii++){
        if(visited[*ii]==false){
            visited[*ii]=true;
            color[*ii]='g';
            dfs(*ii , visited , color);
        }
        else if(visited[*ii]==true && color[*ii]=='g'){
            flag=1;
        }
    }
    color[s] = 'b';
}
int main(){
    int n,m,x,y,i;
    cin>>n>>m;
    for(i=0; i<m; i++){
        cin>>x>>y;
        adj[x].push_back(y);
    }
    bool visited[n+1];
    char color[n+1];
    for(i=0; i<n; i++){
        visited[i] = false;
        color[i] = 'w';
    }
    dfs(0 , visited , color);
    if(flag==1)
    {
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

- Shubham Jindal