使用三色算法进行循环检测与使用集合相比-使用其中一个比另一个有什么优势?

这两个概念上是等价的:集合 S 完全包含灰色节点,否则算法相同。

然而,在实践中,有一些细微的差别:

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

在性能关键的情况下,颜色方法对于线性运行时具有较小的常量因子。但如果添加 color int 或 String S(相对于A Node 通过添加字段的可能性来初始化),那么set方法将更易于编码,因为您可以避免更改节点的表示形式。