在DFS中为顶点使用3种状态有什么好处？ [英] What's the good of using 3 states for a vertex in DFS?

问题描述

在《坚果壳算法》（第二版）中对深度优先搜索（DFS）的解释中，作者使用了3种状态表示顶点，例如 white （未访问），灰色（有未访问的邻居），黑色（已访问）。

In the explanation of depth-first search (DFS) in Algorithms in a Nutshell (2nd edition), the author used 3 states for a vertex, say white(not visited), gray(has unvisited neighbors), black(visited).

两个状态（白色和黑色）足以进行遍历。为什么要添加灰色状态？

Two states (white and black) are enough for a traverse. Why add the gray state? What's it used for?

推荐答案

这是Da算法的一种变体，显示在 Coerman等人的算法简介。

This is a variation of the DFS algorithm shown in Introduction to Algorithms by Coerman at al.

当您使用3种颜色代替时只有2个，它为您提供了更多信息。拳头，它使您可以在算法运行期间的每个点上，了解哪些顶点当前为打开（灰色），哪些顶点为闭合（黑色）和哪些尚未探索（白色）。

When you use 3 colors instead of only 2, it gives you more information. Fist, it allows you at each point during the algorithm run, to know which vertices are currently "open" (gray), which are "closed" (black) and which are unexplored yet (white).

此外，当您使用3种颜色的DFS的着色的时间戳记（这是一个列表，表示按每个顶点的出现顺序对每个顶点进行着色）时，您会发现有关以下内容的有趣属性该图，如后沿。

In addition, when you use "timestamping" of the colorings (which is a list saying when you color each vertex in the order it occurd) of DFS using 3 colors - you can find out interesting properties about the graph, like backedges. This is used for example to determine if a graph is acyclic or not.

请注意，仅出于发现图形的目的-这3种颜色确实不是强制性的，并且确实练习22-3.4要求您证明这一点。

Note that for the sole purpose of discovering a graph - the 3 colors are indeed not mandatory, and indeed exercise 22-3.4 asks you to show that.

这篇关于在DFS中为顶点使用3种状态有什么好处？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！