Loading... **生成树**是和原图点集相同，树形态的子图。 树是一个整体（霍格沃兹除外），而图可能不连通。生成树一定是连通的，不连通的图可以组成**生成森林**。 **最小生成树**即边权之和最小的生成树。 最小生成树其实是**最小权重生成树**的简称。（百度百科） ## Kruskal算法 **定理：最小生成树一定包含图中权值最小的边。** 上述定理是Kruskal算法的灵魂，所有操作都是基于此定理的。我们不断找出图中权值最小的边，合并这条边的两个端点。 这种操作叫做**缩点**。起初，连通图中的每个点各自构成一个集合，我们不断找出当前图中的权值最小边，合并这条边两端点分别所在的集合。重复这样操作，直到图上只剩一个点。 没错，就是并查集。 <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://www.coco07.com/index.php/114.html" target="_blank" class="post_inser_a no-external-link"> <div class="inner-image bg" style="background-image: url(https://coco07.com/usr/uploads/2020/07/3032538077.png);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">并查集</p> <div class="inster-summary text-muted"> 我喜欢并查集，实用、可扩展、效率高并查集GET 查询一个元素属于哪个集合Merge 把两个集合合并成一个大集合以上... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> 下面的图片演示了缩点这一操作。  请看参考代码 ```cpp #include <cstdio> #include <algorithm> struct Node{ int x, y, z; } e[10005]; //边集 inline bool cmp(const Node &a, const Node &b){ return a.z < b.z; } int n/*点数*/, m/*边数*/, f[105]; void init(){ for(int i = 0; i <= n; ++i){ f[i] = i; } } int get(int x){ if(x == f[x]) return x; return f[x] = get(f[x]); } void merge(int x, int y){ f[get(x)] = get(y); } int kruskal(){ init(); std::sort(e, e+m, cmp); int sum = 0, tot = 0; for(int i = 0; i < m; ++i){ if(get(e[i].x) != get(e[i].y)){ sum += e[i].z; merge(e[i].x, e[i].y); if(++tot == n-1) break; } } return sum; } int main(){ scanf("%d%d", &n, &m); for(int i = 0; i < m; ++i){ int a, b, w; scanf("%d%d%d", &a, &b, &w); e[i] = (Node){a, b, w}; } printf("%d\n", kruskal()); return 0; } ``` ## Prim算法 *运行Prim算法，如同守护一棵小树成长。看着它由1个点长到了n个点。* Kruskal算法基于边，Prim算法基于点，Prim算法更适合稠密图。相较之下，Kruskal算法的效率更高。这里只简单介绍一下Prim算法。 将图中的顶点分为两个集合：已选取的点和未选取的点。接下来选取端点分别在两个集合的最短边，将端点加入已选取的点的集合，并退出原来的集合，直到所有点被选取。  © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
