最小生成树问题

Question

老师 想问一下有没有什么算法可以求一个图的所有最小生成树呢

Answer 1

liuyubobobo 2022-08-23 01:49:22

无论是 Kruskal 算法或者 Prim 算法都可以。无论是 Kruskal 算法还是 Prim 算法，在每一步都是基于一定条件，选择一条最短的边。如果当前最短边的选择有多条，先任意选择一条边计算；然后基于这条边的计算结束以后，回溯回来，再选择另一条计算即可。也就是整体变成了一个回溯算法。

但是要注意，这个算法是指数级的。这是因为，一个图的最小生成树的数量本身，就是指数级的。

要理解这一点，可以看这样一个例子（再下面的例子中，每个边的权值都是 1）：

这样一个图，最小生成树有三个（任意选两条边）：

0
| \
|  2
| / 
1

下面的这张图，添加了两个点，三条边以后，最小生成树有 9 个：

0      3
| \  / |
|  2   |
| /  \ |
1      4

因为 0, 1, 2 这个子图的最小生成树有 3 个；2 3 4 这个子图的最小生成树有 3 个；

这两部分的最小生成树可以任意组合成整个图的最小生成树，所以一共有 9 个。

你可以想象，在这张图中，我任意加两个新的顶点，和一个已有的顶点，形成一个三角形（也就是再加三条边），整张图的最小生成树的个数就翻了 3 倍。所以，他是指数上升的。

==========

这个道理和这里这个问题有些像：https://coding.imooc.com/learn/questiondetail/x5yVlPmlVjB64g0R.html

也正是因为这个原因，大多数问题就是让你求解最小生成树的权值，或者得到任意一颗最小生成树就好；而不会枚举所有的最小生成树。

不排除一些问题因为题目的一些特殊限制，导致解的数量不是指数级别的，那就需要具体问题具体分析了。

或者你遇到的问题，你认为需要枚举所有的最小生成树，但其实有其他方法，不需要。

继续加油！：）

• 提问者 qq_站在人群里挺傻_03929303 #1

  get了，非常感谢老师的回答。我好好研究下老师讲的思路