在图中检测周期（使用三种颜色机制）

Question

我知道如何使用三种颜色（黑色，白色和灰色）机制来检测图形中的周期。对于那些谁不知道这一点，请按照此： http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

简而言之，白色节点是这是未被发现的节点，灰色是其正在处理和黑色节点是被发现的那些节点。

几天前，一位老人问我为什么需要三种颜色才能达到这个目的。为什么我们不能只用黑与白呢？为什么灰色节点真的需要？我不好意思向他回答这个问题。你们中的任何一个人都可以告诉我他是问我一个有效的问题还是只是测试我？

Answer 1

不，他没有测试你。您可以使用两种颜色在图表中检测周期，但在这种情况下图必须是无向的。
如果您没有得到原因，请在评论中提问。
编辑
阐述：
我想强调的是，图是路边缘的基础上2种指向，当我们有一个曲线图，当我们人的边缘前进以及后退在两个顶点之间，图的类型称为无向图。

而下面的图片是有向图。

这两个上纸不同的方式是，我们不画边的方向在无向图中，当我们说存在在无向图的上下文节点A和B之间的边缘，它会自动得出为什么我们谈论反向边缘，原因在于计算机程序中边缘以不同表示方式表示的方式，我们仅指示有向边缘，例如在邻接列表中，节点B将在A的邻接列表中只有存在从A到B的边时，如果需要表明存在从B到A的边，那么我们还需要在B的邻接列表中添加节点A.

类似地，在基于邻接矩阵的表示的情况下，矩阵关于其前导对角线（从左上开始的对角线）对称，以示出对于从A存在到B的每条边，还存在从B到A的边。
所以要实现我们以下

所以，你该更换无向图的所有边后，您会看到计算机的代表图的实际图片的任何无向图。

现在假设你已经被给出了一个图。你必须问哪一个？

无向图
我将在参考交谈第一张图片贴在这里。并假定邻接表表示已被用来表示图。

这将是怎样的？
这里你可以看到：

A：B - > d - >电子 - > NULL
B：A - > d - >电子 - > NULL
C：d - > NULL
d：一 - >乙 - “ç - > NULL
E：A - >乙 - > NULL

的目标是设计出一些策略来检查周期存在与否。
现在假设这些节点代表城市中的一些商店，并且边缘是道路，所以如果您看到从节点A到B的道路，则自动存在从B到A的道路，因为图形是无向的。从邻接列表中也可以看出这一点。
要检测无向图中的一个循环，我们将按照以下过程以一种方式进行，一个典型的程序将遵循。然后你会看到我给出的陈述是有效的。那么我们开始吧。
我们从节点A开始，以心情遍历整个图形，遍历这里意味着你想要访问所有的商店。现在要真正了解你访问过的所有商店，当你离开它们时，你会着色它们，所以你站在节点A，现在你有很多从节点A出现的道路，你可以去其他地方去。所有这些选项都出现在A的邻接列表中。
假设您选择一条通往节点B的道路，然后沿着它前进，离开A，在离开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的路径，因此是循环。

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

你可以说我已经在这个特定的例子中展示过它，所以过程可能不会总是起作用，但是尝试通过遍历的感觉来实现我描述的情况，并且试着说服自己，如果你从一个节点开始一组道路，如果你到达某处并且看到该节点是有颜色的，这意味着你已经访问了该节点，并且因为你避免访问该节点的父节点，所以你可以看到一个节点着色的唯一方法是由于某个循环。

我让你知道为什么这个东西不能在有向图中工作，双向边的机制在哪里来到这里。

Answer 2

这里是你的解释，你需要

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

基本上，白色节点变成灰色您访问后的第一次，但灰色节点变成黑色毕竟只有他们的邻居变成了黑色，或者他们没有任何未访问过的邻居。

在有向图中，当且仅当在其所有后代已被访问之前再次看到一个节点时，存在循环。换句话说，如果一个节点有一个灰色的邻居，那么就有一个周期（而不是当邻居是黑色的时候）。灰色节点意味着我们正在探索它的后代 - 如果一个这样的后代对这个灰色节点有边缘，那么就有一个循环。因此，对于有向图中的周期检测，您需要有3种颜色。

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