algorithm - 如何在无向图上运行 BFS 后构建 BFS 树？

Question

我有一个无向图，我从中重新绘制了相同的图，但采用树状结构(具有层次)。我知道广度优先搜索 (BFS) 算法的工作原理，但我不确定如何从图 --> 树进行转换。

在这里，在 this Wikipedia article ，如果向下滚动一点点，您会看到两张德国城市的图片。即使在阅读了那里的伪代码之后，我还是不明白你是如何从第一张图片到第二张图片的。

Answer 1

从图中获取 BFS 树的一种标准方法是运行 BFS，并在执行此操作时保留一个表，将图中的每个节点映射到树中的父节点。您按如下方式填充它:源节点没有父节点(毕竟它是根节点)。然后，每当您处理节点 u 并探索其未探索的邻居 v 之一时，您将 v 的父节点设置为 u。试着在一些小例子上追踪这一点，你会发现这隐含地构建了树，除了边缘向后(边缘从 child 指向 parent 而不是相反)。然后，您只需反转边即可取回 BFS 树。

希望这对您有所帮助!