c++ - 查找给定根的所有生成树

Question

如何使用呼吸优先搜索从起始顶点查找所有可能的生成树。不止一个。

Answer 1

如果您正在寻找所有可能的生成树，那么您实际上不需要执行 BFS。您可以将每条边的权重设置为 1，然后运行一个算法来查找图中的所有最小生成树。

这是有效的，因为所有生成树都有V-1边（其中V表示顶点数）。由于我们将所有边的权重设置为 1，因此每棵生成树都是最小生成树！

编辑：由于您只寻找从某个根开始的生成树，您可以使用深度优先搜索来解决这个问题。

以起始节点为根目标执行深度优先搜索过程。您可以扩充该过程以仅连接不同组件中的节点。