【算法】最小生成树的解法

最小生成树

---

定义

关于N个点用其中的N-1条边连起来的权值最小的图

---

算法

prim

类似Dijkstra和贪心的思路

取一个点为起点遍历所有与其连接的点把最小权值的点加入最小生成树修改于其相连的点权值重复1,2,3直到N次循环 例题： 洛谷P3366：最小生成树模板

https://www.luogu.org/problemnew/show/P3366

代码：

#include<iostream> #include<cstring> using namespace std; int g[5005][5005]; int minn[200001];//存蓝点i与白点相连的最小边 bool exist[5005];//判断是否加入树中 int n,m,x,y,z; int tot; int main() { cin>>n>>m; memset(g,127,sizeof(g)); for(int i=1;i<=m;i++) { cin>>x>>y>>z; //g[x][y]=z; //g[y][x]=z;原程序 if(z<g[x][y])// 这题有重边所以取最小的边 g[x][y]=g[y][x]=z; } memset(minn,127,sizeof(minn)); minn[1]=0;//从1开始 for(int i=1;i<=n;i++) { int k=0; for(int j=1;j<=n;j++) { if(exist[j]==0&&minn[k]>minn[j])//找到与白点相连的最小蓝点 k=j; } exist[k]=1;//将蓝点k加入树中 标记为白点 tot+=minn[k];//计算权值和 for(int j=1;j<=n;j++) { if(exist[j]==0&&g[k][j]<minn[j])//修改与k相连所有的蓝点 minn[j]=g[k][j]; } } cout<<tot; }

---

kruskal

把边用万能的sort从小到大排一遍从小到大挑边合并运用并查集的思路直到有N-1条边 并查集blog：

https://blog.csdn.net/broken_string_/article/details/79947105

代码： 例题同上

#include<iostream> #include<algorithm> using namespace std; struct edge { int l,r,w;//左端点 右端点 权值 }e[200001]; int father[5001]; int n,m,k=0,tot; bool cmp(const edge &a,const edge &b)//用权值排序 { if (a.w<b.w) return 1; else return 0; } int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } void unionn(int x,int y) { int fa=find(x); int fb=find(y); if(fa!=fb) father[fa]=fb; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<=m;i++) { cin>>e[i].l>>e[i].r>>e[i].w; } sort(e+1,e+1+m,cmp); for(int i=1;i<=m;i++) { if(find(e[i].l)!=find(e[i].r)) { unionn(e[i].l,e[i].r); tot+=e[i].w; k++; } if(k==n-1) break;//到n-1条时退出 } cout<<tot; }

转载于:https://www.cnblogs.com/BrokenString/p/9279524.html