algorithm - 在 CLRS 中的 DFS 和 BFS 实现中使用灰色的目的是什么？

Question

在 DFS 和 BFS 的实现中，CLRS 作者为每个顶点区分了 3 种颜色——灰色、黑色和白色。我知道黑白表示节点是否被访问。为什么我们需要灰色？

我的猜测是检测周期，但我们也可以检测只有黑白（即没有灰色）的周期吗？

Answer 1

主要原因是为了帮助读者更好地理解这个概念。但是有一些算法实际上利用了灰色节点。例如，要在有向图中查找循环，您需要灰色节点，因为拥有黑色邻居并不表示循环，只有灰色邻居会创建循环。

A->B, B->C, A->C

A->CC尽管是黑色的，但不会产生循环。