本文主要是介绍最小生成树之kruscal算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这几天留校疯狂学习，想起来了好多已经忘干净的算法，今天看了最小生成树的一些东西，和大家分享一下
#include <iostream>
#include <algorithm>
#define MAXM 1000
using namespace std;int N,M;
int fa[MAXM];//每个结点的父结点记录
struct edge{int x,y,w;edge(int x = 0,int y = 0,int w = 0):x(x),y(y),w(w){}
}e[MAXM];//边的信息（连接x和y，权值为w）int getfather(int x)//查找代表元素（如果本身就是代表元素，返回本身，否则向上继续查找父节点，直到找到代表元素）
{return x == fa[x] ? x : getfather(fa[x]);
}bool cmp(const edge & a, const edge & b)//cmp函数重写
{return a.w < b.w;
}int kruscal()
{sort(e ,e + M ,cmp);//将边按权值大小递增排列int cnt = N;int ans=0;for(int i = 1;i <= N;++i) fa[i] = i;//初始化并查集（即每个元素的父结点都是其本身）for(int i = 0;i < M;++i){int t1 = getfather(e[i].x);//查找代表元素int t2 = getfather(e[i].y);if(t1 != t2)//是否成环（查找到的祖先如果相同，再联一条边就会成环）{fa[t1] = t2;//并操作ans += e[i].w;//结果累加//if (cnt == 1) break;}}return ans;
}int main()
{int res;cin >> N >> M;for(int i = 0;i < M;i++){cin >> e[i].x >> e[i].y >> e[i].w;}res = kruscal();cout << res << endl;return 0;
}
Sample Input
6 6
1 2 1
2 3 2
2 4 2
2 4 3
3 5 4
4 5 5
5 6 6
Sample Output
16
这篇关于最小生成树之kruscal算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
