---恢复内容开始---
最小生成树的算法分为 prim和kruscal算法
初始状态：
设置2个数据结构：
lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边，当mst[i]=0表示起点i加入MST
我们假设V1是起始点，进行初始化（*代表无限大，即无通路）：
lowcost[2]=6，lowcost[3]=1，lowcost[4]=5，lowcost[5]=*，lowcost[6]=*
mst[2]=1，mst[3]=1，mst[4]=1，mst[5]=1，mst[6]=1，（所有点默认起点是V1）
明显看出，以V3为终点的边的权值最小=1，所以边<mst[3],3>=1加入MST
此时，因为点V3的加入，需要更新lowcost数组和mst数组：
lowcost[2]=5，lowcost[3]=0，lowcost[4]=5，lowcost[5]=6，lowcost[6]=4
mst[2]=3，mst[3]=0，mst[4]=1，mst[5]=3，mst[6]=3
明显看出，以V6为终点的边的权值最小=4，所以边<mst[6],6>=4加入MST
此时，因为点V6的加入，需要更新lowcost数组和mst数组：
lowcost[2]=5，lowcost[3]=0，lowcost[4]=2，lowcost[5]=6，lowcost[6]=0
mst[2]=3，mst[3]=0，mst[4]=6，mst[5]=3，mst[6]=0
明显看出，以V4为终点的边的权值最小=2，所以边<mst[4],4>=4加入MST
此时，因为点V4的加入，需要更新lowcost数组和mst数组：
lowcost[2]=5，lowcost[3]=0，lowcost[4]=0，lowcost[5]=6，lowcost[6]=0
mst[2]=3，mst[3]=0，mst[4]=0，mst[5]=3，mst[6]=0
明显看出，以V2为终点的边的权值最小=5，所以边<mst[2],2>=5加入MST
此时，因为点V2的加入，需要更新lowcost数组和mst数组：
lowcost[2]=0，lowcost[3]=0，lowcost[4]=0，lowcost[5]=3，lowcost[6]=0
mst[2]=0，mst[3]=0，mst[4]=0，mst[5]=2，mst[6]=0
很明显，以V5为终点的边的权值最小=3，所以边<mst[5],5>=3加入MST
lowcost[2]=0，lowcost[3]=0，lowcost[4]=0，lowcost[5]=0，lowcost[6]=0
mst[2]=0，mst[3]=0，mst[4]=0，mst[5]=0，mst[6]=0
至此，MST构建成功，如图所示：
1 #include <iostream> 2 3 using namespace std; 4 5 #define MAX 100 6 #define MAXCOST 0xfffffff 7 8 int graph[MAX][MAX]; 9 int lowcost[MAX]; 10 int mst[MAX]; 11 int n,sum = 0; 12 13 int prim() 14 { 15 int min,minid; 16 for (int i=2;i<=n;i++) 17 { 18 lowcost[i] = graph[1][i]; 19 mst[i] = 1; 20 } 21 mst[1] = 0; 22 for (int i=2;i<=n;i++) 23 { 24 min = MAXCOST; 25 minid = 0; 26 for (int j=2;j<=n;j++) 27 { 28 if (lowcost[j] < min && lowcost[j]!=0) 29 { 30 min = lowcost[j]; 31 minid = j; 32 } 33 } 34 sum += min; 35 lowcost[minid] = 0; 36 for (int j=2;j<=n;j++) 37 { 38 if (graph[minid][j] < lowcost[j]) 39 { 40 lowcost[j] = graph[minid][j]; 41 mst[j] = minid; 42 } 43 } 44 } 45 return sum; 46 } 47 48 int main() 49 { 50 int m; 51 cin >> n >> m; // n代表图的顶点，m代表图的边 52 //初始化图 53 for (int i=1;i<=n;i++) 54 { 55 for (int j=1;j<=n;j++) 56 { 57 graph[i][j] = MAXCOST; 58 } 59 } 60 //构造图 61 for (int k=1;k<=m;k++) 62 { 63 int i,j,cost; 64 cin >> i >> j >> cost; 65 graph[i][j] = graph[j][i] = cost; 66 } 67 cout << prim() << endl; 68 return 0; 69 }
kruscal算法 是使用了并查集。始终选择当前可用的最小边权的边（可以直接快排或者algorithm的sort）。每次选择边权最小的边链接两个端点是kruskal的规则，并实时判断两个点之间有没有间接联通。
同样的，模拟过程
对权值进行排序，随后选取最小对权值的边。
排序后，最小的边自然是第8条边，于是4和6相连
遍历继续，第二小的边是1号，1和2联通。
再继续
继续
其次是dis为15的边4，但是2和4已经相连了，pass。
然后是dis为16的两条边（边2和边9），边2连接1和3，边9连接3和6，它们都已经间接相连，pass。
再然后就是dis为22的边10，它连接5和6，5还没有加入组织，所以使用这边。继续，发现此时已经连接了n-1条边，结束，最后图示如下：
#include <iostream> #include <algorithm> using namespace std; #define MAX 100 #define MAXCOST 0xfffffff int fa[MAX]; int weight; struct Node { int l,r,w; }; int init() { for (int i=0;i<MAX;i++) { fa[i] = i; } weight = 0; } bool cmp(struct Node a, struct Node b) //从小到大排列 { return a.w < b.w; } int find(int x) { return fa[x] = (fa[x]==x)?x:find(fa[x]); } void unite(int x,int y) { int a = find(x); int b = find(y); if (a!=b) fa[a] = b; } int main() { int k,n; scanf("%d",&n); getchar(); init(); k = 0; struct Node a[n]; for (int i=0;i<n;i++) { cin >> a[k].l >> a[k].r >> a[k].w; k++; } sort(a,a+k,cmp); for (int j=0;j<k;j++) { if (find(a[j].l)!=find(a[j].r)) { weight += a[j].w; unite(a[j].l,a[j].r); } } cout << weight << endl; return 0; }
该博客借鉴了许多别的博客，之所以写成自己的只是方便自己现在去理解和今后复习
原文：https://www.cnblogs.com/-Ackerman/p/10822909.html
