运行 BFS 后如何在无向图上构建 BFS 树？
How to build a BFS tree after running BFS on an undirected graph?
我有一个无向图，我从中重新绘制了相同的图，但采用树状结构（具有层次）。我知道广度优先搜索 (BFS) 算法的工作原理，但我不确定如何从图 --> 树进行转换。
在这里，在 this Wikipedia article 中，如果向下滚动一点点，您会看到两张德国城市的图片。即使在阅读了那里的伪代码之后，我还是不明白你是如何从第一张图片到第二张图片的。
从图中获取 BFS 树的一种标准方法是 运行 BFS，并且在这样做时，保持 table 将图中的每个节点映射到它的 parent 在树上。您按如下方式填充它：源节点没有 parent（毕竟它是根节点）。然后，每当您处理节点 u 并探索其未探索的邻居 v 之一时，您将 v 的 parent 设置为 u。试着在一些小例子上追踪这一点，你会发现这隐含地构建了树，除了边向后移动（边指向从 children 到 parents 而不是相反的方向).然后，您只需反转边即可取回 BFS 树。
希望对您有所帮助！
我有一个无向图，我从中重新绘制了相同的图，但采用树状结构（具有层次）。我知道广度优先搜索 (BFS) 算法的工作原理，但我不确定如何从图 --> 树进行转换。
在这里，在 this Wikipedia article 中，如果向下滚动一点点，您会看到两张德国城市的图片。即使在阅读了那里的伪代码之后，我还是不明白你是如何从第一张图片到第二张图片的。
从图中获取 BFS 树的一种标准方法是 运行 BFS，并且在这样做时，保持 table 将图中的每个节点映射到它的 parent 在树上。您按如下方式填充它：源节点没有 parent（毕竟它是根节点）。然后，每当您处理节点 u 并探索其未探索的邻居 v 之一时，您将 v 的 parent 设置为 u。试着在一些小例子上追踪这一点，你会发现这隐含地构建了树，除了边向后移动（边指向从 children 到 parents 而不是相反的方向).然后，您只需反转边即可取回 BFS 树。
希望对您有所帮助！