代码之家 › 专栏 › 技术社区 › quantummidget

正在查找BFS父关系数组

breadth-first-search graph-theory parent-child

quantummidget · 技术社区 · 8 年前

我是一名学生,目前正在研究DFS和BFS图形。在为本课程做在线实验室时,我遇到了这个问题

完成从顶点5开始的BFS后,父关系(数组)为[\u,\ u,\ u,\ u,\ u,\ u,\ u]

所讨论的图表写为:

U 6
0 4
5 4
4 2
2 3
3 0
3 4

给出的答案(我通过猜测和检查最终发现)是:
[4,无,4,4,5,无]

我可能误解了图形遍历的一些基本原理,但在花了半个多小时的时间搜索之后,我仍然找不到这个答案的原因,因此非常感谢您的帮助。

1 回复 | 直到 7 年前

quantummidget 8 年前

父阵列中的每个间隙表示每个顶点。在上面的示例中,当源顶点为5时,顶点0、2、3的父顶点为顶点4,因此父数组中的点0、2和3具有指定给它们的值4。类似地,顶点4有5作为父对象,因此数组也会这样。最后,顶点1和5没有父节点,1是因为它与图形断开连接,5是因为它是本例中的源节点。因此,这些顶点在阵列中标记为“无”。希望这能帮助任何遇到同样问题的人。

推荐文章

Bob · BFS用映射C替换数组++

8 年前

quantummidget · 正在查找BFS父关系数组

8 年前

Ganpat · BFS中队列大小的重要性

8 年前

R A · python中的BFS实现速度不够快

8 年前

Fueled By Coffee · 检测循环依存关系

8 年前

DK100 · 在广度优先搜索中处理重复节点

8 年前

Garrick · 邻接表表示的时间复杂度?

9 年前

Upender Reddy · 从左上角到右下角单元格的最小路径,在这里我们可以在北、南、东、西方向进行遍历

10 年前

César Vallejo · 将宽度优先搜索更改为深度优先搜索,N-Queen解算器

10 年前

Ankit Mishra · 图与BFS和DFS树的等价性

10 年前