algorithm - 维基百科的广度优先搜索示例 : How is a parentless node reached?

Question

现在维基百科的 pseudo-code for BFS很清楚，我进一步查看了该条目中提供的图形示例，但有一个小细节我不太明白。

在原始树中，Stuttgart 看起来没有父项。也就是说，它既不与根(Frankfurt)相邻，也不与同一行/级别上的其他节点(Mannheim 和 Wurzburg 相邻) >):

我的问题是:如果没有从树的根部到它的路径，它是如何到达/遍历它的，这样它最终会被正确处理产生结果树？

Answer 1

这里的问题是，您正在考虑的树实际上是图。在图中，父节点和子节点的概念没有多大意义，与“级别”的概念相同(除非您将其视为将节点与根分开的边数):对于每个顶点(最多常见实现)你有一个代表所有相邻顶点的列表，你可以在 DFS 或 BFS 搜索中迭代该列表以探索结构。在这里，Stuttgart 出现在 Nurnberg 的邻接列表中，并且可以从那里到达(Nurnberg 是否“向上”无关紧要，这只是一个图形表示)。