在DFS中为顶点使用3个状态有什么好处？
nn0*_*n0p 8 algorithm depth-first-search graph-algorithm
在Nutshell算法(第2版)中深度优先搜索(DFS)的解释中,作者使用了3个状态用于顶点,比如白色(未访问),灰色(具有未访问的邻居),黑色(访问).
两个状态(白色和黑色)足以进行遍历.为什么要添加灰色状态？它用于什么？
这是Coerman 等人的《算法简介》中所示的 DFS 算法的变体。
当您使用 3 种颜色而不是 2 种颜色时，它会为您提供更多信息。首先，它允许您在算法运行期间的每个点知道哪些顶点当前是“开放”（灰色）、哪些顶点是“闭合”（黑色）以及哪些顶点尚未探索（白色）。
此外，当您使用 3 种颜色的 DFS 着色“时间戳”（这是一个列表，说明您何时按照每个顶点出现的顺序为其着色），您可以找到有关图形的有趣属性，例如后边。例如，这用于确定图是否是非循环的。
请注意，仅出于发现图表的目的 - 3 种颜色确实不是强制性的，而且练习 22-3.4 确实要求您展示这一点。