首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >BFS algorithm Introduction to algorithms,leiserson etal著

BFS algorithm Introduction to algorithms,leiserson etal著
EN

Stack Overflow用户
提问于 2010-12-16 16:43:04
回答 3查看 2.3K关注 0票数 3

在书中,为了解释BFS算法,他们假设每个顶点可以有三种颜色中的一种:白色、灰色和黑色。白色表示尚未访问过的顶点,灰色表示已访问过但可能有一些相邻顶点尚未访问过的顶点,黑色表示所有相邻顶点都已访问过的顶点。我不明白他们为什么要用三种颜色。我们可以使用2种颜色来创建BFS算法:1种颜色用于已访问的顶点,1种颜色用于未访问的顶点。为什么我们需要第三种颜色。它解决了什么问题?

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2010-12-17 00:40:39

基本的BFS不需要3种颜色,但灰色和黑色节点之间的区别在教学上很有用,因为灰色节点仍然在队列中,而黑色节点已经完成。

票数 2
EN

Stack Overflow用户

发布于 2012-01-15 08:45:18

这本书的第三版(2009)有一个脚注,说两种颜色就足够了,练习22.2-3显示了这一点。脚注声称灰色和黑色有助于理解。然而,你的问题和脚注的存在向我表明,至少对我们中的一些人来说,额外的颜色分散了试图理解算法的注意力。

票数 2
EN

Stack Overflow用户

发布于 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种颜色,您将无法在不复制某些边的情况下编写这样的程序。

代码语言:javascript
运行
复制
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}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/4458836

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档