现在维基百科的 pseudo-code for BFS很清楚,我进一步查看了该条目中提供的图形示例,但有一个小细节我不太明白。
在原始树中,Stuttgart
看起来没有父项。也就是说,它既不与根(Frankfurt
)相邻,也不与同一行/级别上的其他节点(Mannheim
和 Wurzburg
相邻) >):
我的问题是:如果没有从树的根部到它的路径,它是如何到达/遍历它的,这样它最终会被正确处理产生结果树?
最佳答案
这里的问题是,您正在考虑的树实际上是图。在图中,父节点和子节点的概念没有多大意义,与“级别”的概念相同(除非您将其视为将节点与根分开的边数):对于每个顶点(最多常见实现)你有一个代表所有相邻顶点的列表,你可以在 DFS 或 BFS 搜索中迭代该列表以探索结构。 在这里,Stuttgart 出现在 Nurnberg 的邻接列表中,并且可以从那里到达(Nurnberg 是否“向上”无关紧要,这只是一个图形表示)。
关于algorithm - 维基百科的广度优先搜索示例 : How is a parentless node reached?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34048253/