No.1 概念
想了解最小生成树,首先得明白什么是生成树。
生成树的概念:包含连通图中所有的顶点,且任意两顶点之间有且仅有一条通路。
那什么是最小生成树?
最小生成树(Minimum Spanning Trees)的概念:连通图的一颗生成树(Spanning Tree)是包含图的所有顶点的连通无环子图(也就是一棵树)。加权连通图的一颗最小生成树是图的一颗权重最小的生成树,其中,树的权重定义为所有边的权重总和。最小生成树问题就是求一个给定的加权连通图的最小生成树问题。
直接地讲,它就是在无向图中选择边把图的所有的节点连接成一棵树,要求边权之和最小。
No.2 Prim算法
1)Prim算法是什么?
Prim算法通过一系列不断扩张的子树来构造一棵最小生成树。
2)Prim算法的思想
- 我们从图的顶点集合中任意选择的一个单项点,作为序列中的初始子树。
- 每一次迭代时,以一种贪心的思想来扩张当前的生成树,即把不在树的最近顶点添加到树中(我们所说的最近顶点,是指一个不在树中的顶点,它以一条边权最小的边和树中的顶点相连,而树的形状是无所谓的)。
- 当图的所有顶点都包含在所构造的树中以后,该算法就停止了。
3)Prim算法需注意的点
其实Prim算法的思想和Dijkstra相像,都是分两部分来操作。
4)举栗
如图,我们确定一个起点编号1,将1加入1号阵营。设变量mst求最小生成树。mst此时为0。
顶点编号 | 1 | 2 | 3 | 4 | 5 |
连接边 | 2 | 4 | 5 | 1 | 1 |
边权 | 1 | 2 | 1 | 2 | 3 |
阵营 | 1 | 0 | 0 | 0 | 0 |
找到与1相连边权最小的顶点2,加入1号阵营,mst+=1。
顶点编号 | 1 | 2 | 3 | 4 | 5 |
连接边 | 2 | 4 | 5 | 1 | 1 |
边权 | 1 | 2 | 1 | 2 | 3 |
阵营 | 1 | 1 | 0 | 0 | 0 |
找到与2相连边权最小的顶点4,加入1号阵营,mst+=2。
顶点编号 | 1 | 2 | 3 | 4 | 5 |
连接边 | 2 | 4 | 5 | 3 | 1 |
边权 | 1 | 2 | 1 | 2 | 3 |
阵营 | 1 | 1 | 0 | 1 | 0 |
找到与4相连边权最小的顶点3,加入1号阵营,mst+=2。
顶点编号 | 1 | 2 | 3 | 4 | 5 |
连接边 | 2 | 4 | 5 | 3 | 1 |
边权 | 1 | 2 | 1 | 2 | 3 |
阵营 | 1 | 1 | 1 | 1 | 0 |
找到与3相连边权最小的顶点5,加入1号阵营,mst+=1。
顶点编号 | 1 | 2 | 3 | 4 | 5 |
连接边 | 2 | 4 | 5 | 3 | 1 |
边权 | 1 | 2 | 1 | 2 | 3 |
阵营 | 1 | 1 | 1 | 1 | 1 |
此时,所有顶点已加入确定最小生成树的阵营,退出循环,答案mst为6.
5)Prim算法的优化
Prim算法思想上与Dijkstra算法相似,优化也区别不大。
我们可以定义一个优先队列,队列中元素记录了节点的编号和节点和树中的顶点相连的边权,将源点压入队列。当队列非空,执行以下操作:
1.u等于队顶的节点,w等于队顶节点的最短边权。
2.遍历u的所有边,如果能找到节点v小于v的当前值,更新v,将v压入队列。
以上就实现了优化。
6)核心代码
Code
void Prim(int s){
memset(d,0x3f,sizeof(d));
memset(vis,0,sizeof(vis));
d[s]=0;
q.push(node(s,0));
while(!q.empty()){
int u=q.top().u;
q.pop();
if(vis[u]){
continue;
}
mst+=d[u];
vis[u]=1;
for(int i=0;i<Graph[u].size();i++){
int v=Graph[u][i].v;
long long w=Graph[u][i].w;
if(d[v]>w){
d[v]=w;
q.push(node(v,w));
}
}
}
}
7)Prim算法总结
Prim算法优化后节省了很多时间,用于稠密图,也就是边多的图较好。
No.3 Kruskal算法
1)Kruskal算法是什么?
Kruskal算法按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路
2)Kruskal算法的思想
使用并查集,(并查集是什么?-Link)将加权图每个顶点都看做森林,然后将图中每条邻接边的边权按照升序的方式进行排列,接着从排列好的邻接边表中抽取边权最小的边,写入该边的起始顶点和结束顶点,连接顶点将森林构成树,然后读取起始结束顶点的邻接边,优先抽取边权小的邻接边,继续连接顶点将森林构成树。
添加邻接边的要求是加入到图中的邻接边不构成回路(环)。如此反复进行,直到已经添加n-1条边为止。
3)Kruskal算法的目标
Kruskal根据边权以递增的方式逐渐建立最小生成树,是以边为目标去构建最小生成树。
4)核心代码
Code
void Kruskal(){
sort(ed+1,ed+m+1,cmp);
for(int i=1;i<=m;i++){
int p=FindSet(ed[i].u);
int q=FindSet(ed[i].v);
if(p!=q){
UnionSet(p,q);
mst+=ed[i].bq;
if(si[q]==n){
return;
}
}
}
}
5)Kruskal算法总结
Kruskal算法易理解,易上手,时间复杂度也很低,用于稀疏图,也就是点多的图较好。
完结!文章来源:https://www.toymoban.com/news/detail-411939.html
文章来源地址https://www.toymoban.com/news/detail-411939.html
到了这里,关于图论——最小生成树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!