数据结构—最小生成树_数据结构最小生成树算法
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
目录
一、生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。
边尽可能少但要保持连通
若图中顶点数为n则它的生成树含有n-1条边。对生成树而言若砍去它的一条边则会变成非连通图若加上一条边则会形成一个回路。
一个连通图可能有多个连通树
二、最小生成树代价最小树
对于一个带权连通无向图G=(V, E)生成树不同每棵树的权即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合若T为R中边的权值之和最小的生成树则T称为G的最小生成树Minimum-Spanning-Tree,MST) 。
最小生成树可能有多个但边的权值之和总是唯一且最小的
最小生成树的边数=顶点数–1。砍掉一条则不连通增加一条边则会出现回路
如果一个连通图本身就是—棵树则其最小生成树就是它本身只有连通图才有生成树非连通图只有生成森林
三、求最小生成树
1、Prim算法普里姆
Prim算法普里姆):
从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树直到所有顶点都纳入为止。
具体该如何实现呢以下面的为例
从P城出发找最小生成树,从P城出发。
P到学校的代价最小是1最小所以P城连接学校
然后找那个点到P城和学校形成的树中最小代价的我们可以看到只有矿场到P城是最小的
所以连接P城和矿场。如果选下面的4最终图不一样但是最终最小代价一样
然后看哪个点到这个三个点形成的树最小的代价知道渔村是最小的连接矿场和渔村。
在寻找是剩下俩个结点中到这棵树的最下代价易知是农场到P城的路径最小。
最后还剩一个电站与农场相连路径最短为3 。
这个也是最终的最小生成树红线连接部分
2.Kruskal 算法克鲁斯卡尔
Kruskal算法(克鲁斯卡尔)∶
每次选择一条权值最小的边使这条边的两头连通(原本已经连通的就不选)
直到所有结点都连通
任然是这个图
按照克鲁斯卡尔算法找到一个最小的权值的边是学校和P城
然后在找到是矿场和渔村且俩个点不连通可以选。
然后找权值最小的边是渔村和电站为3且俩个点目前不连通·
在从剩余的边中找到权值最小的有俩个是P城和矿场以及P城和渔村随便选都行。虽然最终图不一样但是最小代价一样。
然后找最小发现是P城和渔村但是P城和渔村是连通的。所以不选在找权值是5的有俩个然而学校和矿场确是俩通的只能选农场和P城选完以后发现全部连通
3.Prim算法和Kruskal算法对比
