最小生成树与Prim算法
最小生成树(MST)
定义
首先是一棵树(废话
其次没有回路(废话
包含全部顶点和V-1条边
边的权重和最小!!!!!
所以如果是单棵最小生成树,至少说明图是连通的。不然就是森林。
生成思路
既然是根据图生成树,那么至少要有遍历图。那么,便要从一个源点出发,来一场愉快的深搜或广搜。
深搜生成就叫DFS树(深度优先搜索树
广搜生成就叫BFS树(广度优先搜索树
我们只需要在if语句中,在递归调用语句之前做一点手脚,便可以达到目的。
Prim算法——让一棵小树长大
(别装了!Dijkstra我知道是你!)
时间复杂度
O(n^2),是根据图生成最小树的算法。
算法思路
是一个穿了马甲的Dijkstra算法。用的是蓝白点的思想。
Dijkstra是啥?https://www.cnblogs.com/Uninstalllingyi/p/10417446.html
每次循环都把一个蓝点u变成白点。并且这个蓝点u与白点相连的边权势当前所有蓝点中最小的min[u]
仔细想想,是贪心的思路哟…
好的,我们来手工模拟一下。求下面这个图的最小生成树。(里面是伪代码哟)
(emm…其实这个是绿白点…没事你就假装一下色盲。)
初始所有的点全都是蓝点,所以说这里有一个数组min[i]来表示一下。那么除了起点,其他的全部初始化为无穷大(0x3f)。即min[1]=0。权值之和用int MST=0来保存。
那么第一次循环就没什么说的了,min[1]=0是最小的蓝点,然后把1变白。然后枚举和a相连的蓝点,修改它们与白点相连的最小边权(就是min数组啦)
min[]=map[][]=;
min[]=map[][]=;
min[]=map[][]=;
第二次循环找到min[2]是最小的蓝点,变白。然后更新相连的蓝点。bulabulabula。
min[]=map[][]=; min[]=map[][]=;
第三次循环…找到min[3]=1是最小的那个…变白…更新蓝点最小值…
min[]=map[][]=;
哦,这里要注意一下,因为min[5]=2<6,所以5不用更新。
第四次循环找到点4,第五次循环找到点5.反正他们也没相连的蓝点了,所以直接变白叭。
那么,最后得到的权值之和是…
min[]+min[]+min[]+min[]+min[]=
++++=;
以1为起点生成最小生成树,min[v]表示蓝点与白点相连的最小边权。
MST表示最小生成树的权值之和。
⑴初始化min[v]=∞(v≠);min[]=;MST=;
⑵for(int i=;i<=n;i++){
①寻找min[u]最小的蓝点u
②将u标记为白点
③MST+=min[u]
④for(int v=;v<=n;v++)//与白点u相连的所有蓝点v
if(w[u][v]<min[v]) min[v]=w[u][v]//注:w[u][v]表示第u行第v个元素。第u行表示和白点u相连的所有的点。
}
⑶算法结束,MST即为最小生成树的权值之和。
高能伪代码
这里有一道洛谷的模板题
https://www.luogu.org/problemnew/show/P3366
#include<iostream>
#include<cstring>
#include<cstdio>
//prim算法
using namespace std;
const int maxx=0x3f3f3f3f;
const int MAXN=;
int n,m,x,y,z,map[MAXN][MAXN],minn[MAXN],MST=,vis[MAXN];
int main(){
scanf("%d%d",&n,&m);
memset(map,0x3f,sizeof(map));
for(int i=;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
if(map[x][y]>z){
map[x][y]=map[y][x]=z;
}
}
memset(minn,0x3f,sizeof(minn));
minn[]=;
for(int i=;i<=n;i++){
int u=;
for(int j=;j<=n;j++){
if(!vis[j]&&minn[u]>minn[j]){
u=j;
}
}
vis[u]=true;
MST+=minn[u];
for(int v=;v<=n;v++){
if(!vis[v]&&map[u][v]<minn[v]){
minn[v]=map[u][v];
}
}
}
printf("%d\n",MST); }
(倒是头一次知道洛谷如果不加cstdio的头文件是不可以用printf的…尴尬。
最新文章
- 普通用户ssh无密码登录设置
- Java算法之字符串反转分析
- 初学python之urllib
- 学习使用 jQuery &; CSS3 制作照片堆栈效果
- 【Spring】Spring系列6之Spring整合Hibernate
- 有关T-SQL的10个好习惯(转)
- JAVA 正则表达式 (超详细)
- org.apache.hadoop.fs-BlockLocation
- css中table-layout:fixed 属性的用法
- jQuery对象与dom对象相互转换jQuery对象与dom对象相互转换
- [AngularJS + Webpack] Production Setup
- Cycling Label
- PPT去掉图片白色背景
- wall time
- angularjs表单
- 关于IT创业和反思
- [leetcode-434-Number of Segments in a String]
- 解决loadrunner录制时 Request Connection: Remote Server @ 0.0.0.0:80 (Service=?) NOT PROXIED! (REASON: Unable to connect to remote server: rc = -1 , le = 0)问题
- redux源码学习笔记 - applyMiddleware
- iis配置asp.net常见问题解决方案