算法学习之路|最小生成树—kruskal

算法概述:一个带权的连通图， 有V个点，E个边，去掉所有的边，得到一个新图，将E个边按权值从小到大排列，然后从权值最小的边<u,v>开始加入,重复下去，但每次加入之前要判断u，v是否连通，若连通则不加入，直到全部连通为止，结束循坏。

代码：

struct Edge {int u;//边起点int v;//边终点int w;//权值 }E[N]; int V;//点数 int E;//边数 bool cmp(const Edge *a ,const Edge *b) { return *(Edge *)a.w - *(Edge *)b.w ; //从小到大排序，把a，b位置反过来就是从大到小 } void kruskal() {int i,j,p,q,k;int _set[N];sort(E,E+N);for(i=0;i<E;i++){_set[i]=i;}k=1;j=0;while (k<E) { p=_set[E[j].u]; q=_set[E[j].v]; if (p!=q) {k++; for (i=0;i<E;i++) { if (_set[i]==q) { vset[i]=p; } } } j++; } }

 

总结

以上是生活随笔为你收集整理的算法学习之路|最小生成树—kruskal的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。