在书中,为了解释BFS算法,他们假设每个顶点可以有三种颜色中的一种:白色、灰色和黑色。白色表示尚未访问过的顶点,灰色表示已访问过但可能有一些相邻顶点尚未访问过的顶点,黑色表示所有相邻顶点都已访问过的顶点。我不明白他们为什么要用三种颜色。我们可以使用2种颜色来创建BFS算法:1种颜色用于已访问的顶点,1种颜色用于未访问的顶点。为什么我们需要第三种颜色。它解决了什么问题?
发布于 2010-12-17 00:40:39
基本的BFS不需要3种颜色,但灰色和黑色节点之间的区别在教学上很有用,因为灰色节点仍然在队列中,而黑色节点已经完成。
发布于 2012-01-15 08:45:18
这本书的第三版(2009)有一个脚注,说两种颜色就足够了,练习22.2-3显示了这一点。脚注声称灰色和黑色有助于理解。然而,你的问题和脚注的存在向我表明,至少对我们中的一些人来说,额外的颜色分散了试图理解算法的注意力。
发布于 2010-12-17 00:46:09
理论上,您可以实现只有2个状态的BFS。在某些情况下,拥有3个状态是有用的。下面是其中的两个:
在计算BFS树时,具有顶点的三个状态(三种颜色)是很有用的。从已发现(D)节点到未发现(U)节点的任何边都是树边。从已发现节点到已处理(P)节点的任何边都是后边。从发现的节点到发现的节点的任何边都是交叉边。
再举一个例子,假设您正在编写一个程序来打印出无向图的所有边。使用3种颜色(U,D,P),您将处理从D到U(您正在发现新顶点)和从D到D(您正在发现兄弟之间的边)的所有边。但是,您不会处理从D到P的任何边,因为这将是BFS用来发现D处节点的边。使用2种颜色,您将无法在不复制某些边的情况下编写这样的程序。
1----2
| |
| |
3----4
BFS starting at 1:
Tree Edges: {1, 2}, {1, 3}, {3, 4}
Cross Edge: {2, 4}
Without three states you will try to process {2, 1}, {3, 1}, {4, 3}, {4, 2}
https://stackoverflow.com/questions/4458836
复制相似问题