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

正在查找BFS父关系数组

breadth-first-search graph-theory parent-child

quantummidget · 技术社区 · 7 年前

我是一名学生,目前正在研究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 回复 | 直到 6 年前

quantummidget 7 年前

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

推荐文章

amonroejj · 实现基于节点的工作流的一般原则,如Unreal、Blender、Alteryx等?

7 年前

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

7 年前

I'm not human · Prolog查找不相关的图形节点

7 年前

WIZARD_ · 无向非加权图的最大顶点对数

7 年前

user9137770 · 邻接列表与邻接矩阵的区别

7 年前

Parth Prajapati · java中的哪个标准库数据结构为实现邻接列表提供了最短的复杂时间?[已关闭]

7 年前

Sook Yee Lim · 在给定邻接矩阵的情况下求两个图的交并?

7 年前

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

7 年前

Keith Pham · 最大化给定预算的子图“价值”

7 年前

Mathochist · 在配对列表中查找最大配对数

7 年前