检测图中的循环（使用三色机制）

Question

我知道如何使用三种颜色（黑色、白色和灰色）机制来检测图表中的循环。对于那些不知道这一点的人，请按照以下步骤操作： http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

简而言之，白色节点是未发现的节点，灰色是正在处理的节点，黑色节点是已发现的节点。

几天前，一位资深人士问我为什么需要三种颜色才能达到这一目的。为什么我们不能只用黑白来做到这一点？为什么真正需要灰色节点？可惜我能回答他这个问题。你们谁能告诉我他是在问我一个有效的问题还是只是在测试我？

Answer 1

不，他不是在考验你。您可以仅使用两种颜色来检测图中的循环，但在这种情况下该图必须是无向的。

阐述

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

下图是一个有向图。

这两者在纸面上的不同之处在于，我们不会在无向图中绘制边的方向，每当我们说在无向图的上下文中节点 A 和 B 之间存在一条边时，就会自动得出反向边也存在。为什么我们甚至谈论反向边缘，原因是在计算机程序中，边缘以不同的表示方式表示，我们仅指示有向边缘，例如在邻接列表中，仅当存在边缘时，节点 B 才会出现在 A 的邻接列表中从A到B，所以在这个表示中，如果我们需要证明也存在从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 ->无效的

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

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

为了检测无向图中的循环，我们将遵循以下过程，一个典型的程序将遵循。然后你就会看到我给出的陈述是如何有效的。那么让我们开始吧。

我们从节点A开始，有心情遍历整个图，这里的遍历意味着你要参观所有的商店。现在，为了真正跟踪您访问过的所有商店，您在离开它们时为它们着色，因此您站在节点 A，现在您有许多从节点 A 出来的道路，您可以沿着它们去其他地方。所有这些选项都出现在 A 的邻接表中。

假设您选择一条通往节点 B 的道路，然后沿着它离开 A，并在离开 A 之前为其着色。现在站在 B 处，你首先看到的是，那个节点是彩色的吗？你看没有！然后你就知道你以前没有访问过这个节点。再次想做同样的事情，所以你看到 B 的邻接列表来选择下一条路，你看到一条通往 A 的路，你再次沿着这条路到达 A，离开时颜色为 B。但是，一旦到达节点 A，您就会看到它被着色，这意味着您以前访问过这家商店，但随后您意识到，由于图是无向的，因此从 B 到达 A 不是问题，因为边是双向的，于是你就原路返回。

为了避免再次出现这种情况，如果您从 j 中发现了 i，则可以使用父数组，其中 par[i] = j。现在你又消除了拜访父母的陷阱。现在你选择从B开始的下一条路，也就是到E，你去那里，给B涂上颜色，这次设置par[E] = B，当你到达E时，你想再次做同样的事情。但是这次你看到一条通往A的路，首先你检查A是你的父母吗？因为你不想再次拜访你的父母，因为你本身就是从那里来的。

这里是“否”。所以你转到 A，但是一旦到达 A，你就会注意到该节点已着色。如果这是真的，那么就意味着你已经访问过 A，这意味着存在一条从 A 出发又到达 A 的路径，因此是一个循环。

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

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

我留给你去认识为什么这个东西在有向图中不起作用，以及双向边缘的机制在哪里。