algorithm - 使用三色算法与使用一组算法进行循环检测 - 使用其中一个比另一个有什么优势？

Question

有这两种看似相似的方法来检测图中的循环:

1. 遍历图形，DFS 风格，假设所有节点都是白色的，直到您第一次访问它们，使它们变成灰色。在节点上完成所有处理后，将其变为黑色。如果您曾经访问过一个灰色节点，您就知道您有一个循环。

2. 以 DFS 样式遍历图形，并保留一个包含 DFS 堆栈中当前所有节点的集合 S(仅出于性能目的)。每次你访问一个节点时，你将它添加到 S，每次你完成一个节点，你将它从 S 中删除。如果在任何时候你试图访问一个已经在 S 中的节点，则存在一个循环。

选择其中一种方案比另一种方案有任何实际优势吗？我可能缺少某种权衡？或者使用一个或另一个导致完全相同？

谢谢

Answer 1

两者在概念上是等价的:集合 S 恰好包含灰色节点，算法在其他方面相同。

然而，在实践中，存在细微差别:

• 如果集合S 是基于散列的实现，则节点必须是可散列的。如果散列函数设计不当，或者数据的选择具有对抗性，那么性能就会受到影响。
• 如果集合S 是基于树的实现，那么节点必须是可比较的。此外，您不再具有(摊销的)恒定时间集合查找。
• 如果使用了颜色，那么节点必须有一个未被用于其他目的的“颜色”字段。但是，这提供了最快的“集合查找”，因为它只是一次查找/比较。
• 如果图形是有向的或断开的，那么你将不得不多次 DFS(从所有的白色节点)。跟踪一个节点是否被访问需要第二个集合，因为第一个集合在 DFS 结束时总是空的。因为实际上有 3 个节点“状态”，所以需要 2 个集合来存储该信息。

在性能关键的情况下，颜色方法将具有更小的线性运行时间常数因子。但是，如果向节点添加 color 字段不是一个选项，那么使用集合是一个不错的选择。如果节点当前被实现为 int 或 String(与可能添加字段的 Node 类相反)，则集合方法将更易于编码，因为您可以避免更改节点的表示。