从给定的根查找所有的跨接树

Question

如何使用 breath-first-search 从一个起始顶点找到所有可能的 spanning 树，而不仅仅是一个。

Answer 1

如果你正在寻找 都 可能的生成树，那么你实际上不需要做BFS。你可以直接将每个边的权重设为1，然后运行一个算法，找到图中所有最小的生成树。

这样做是可行的，因为所有的生成树都有 V-1 边缘（其中 V 代表顶点的数量）。) 由于我们设置所有的边的权重都是1，所以每一棵生成树都是一棵最小生成树!

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

以起始节点作为根目标执行深度优先搜索过程。你可以增强程序，只连接处于不同组件的节点。