一.最小生成树
之前学习的加权图，它的边关联了一个权重，那么就可以根据这个权重解决最小成本问题，但如何才能找到最小成本对应的顶点和边呢？最小生成树相关算法可以解决。
1.1.最小生成树定义及约定
定义： 图的生成树是它的一棵含有其所有顶点的无环连通子图
一副加权无向图的最小生成树 是它的一棵权值(树中所有边的权重之和)最小的生成树
约定：
①只考虑连通图。最小生成树的定义说明它只能存在于连通图中，如果图不是连通的，那么分别计算每个连通图子图的最小生成树，合并到一起称为最小生成森林。
②所有边的权重都各不相同。如果不同的边权重可以相同，那么一副图的最小生成树就可能不唯一了，虽然我们的算法可以处理这种情况，但为了好理解，我们约定所有边的权重都各不相同。
1.2. 最小生成树的原理
性质：
- 用一条边接树中的任意两个顶点都会产生一个新的环；
- 从树中删除任意一条边，将会得到两棵独立的树；
要从一副连通图中找出该图的最小生成树，需要通过切分定理完成。
切分：
将图的所有顶点按照某些规则分为两个①非空 ②没有交集的集合。
横切边：
连接两个属于不同集合的顶点的边称之为横切边。
例如我们将图中的顶点切分为两个集合，灰色顶点属于一个集合，白色顶点属于另外一个集合，那么效果如下：
//连接两个集合中间的 黑线，就是横切边
切分定理：
在一副加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图中的最小生成树。
注意: 一次切分产生的多个横切边中，权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边。
横切边中属于最小生成树的边可能不止一条
要切分多次，每次切分的权重最小的边不一样，所以横切边中属于最小生成树的边不唯一。
二.贪心算法
贪心算法是计算图的最小生成树的基础算法，它的基本原理就是切分定理，使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边。如果图有n个顶点，那么需要找到n-1条边，就可以表示该图的最小生成树。
即通过切分，找到每次切分后的横切边中 权重最小的边，此边就属于最小生成树 !
进行n-1次切分后，找到最小生成树的所有边！即切到最小权重的横切边能够连接所有顶点为止！
经过n-1次切分，每次切分的最小权值的横切边能把所有顶点都连起来，则找到了最小生成树。
注意：
寻找最小生成树的算法有多种，贪心算法是最基础的一种。其他算法都可以看作贪心算法的一种特殊情况。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89353.html
