做旅游计划的网站/百度快速收录办法

怎样构造最小生成树在大二上学期的离散数学中就已经学过了，我们当时就是使用的算法就是Kruskal算法。

Kruskal算法：

Kruskal算法按照边的权值的顺序从小到大查看一遍，如果不产生圈，就把当前这条边加入到生成树中。其实就是贪心的一种思想。

这里我们就需要解决一个问题，怎样判断是否产生圈，那么就需要并查集的方法了。假设现在要把连接顶点u和顶点v的边e加入到生成树中。如果加入之前u和v不在一个集合中，那么加入e就不会产生圈，否则就会产生圈。

初始情况，各自独立

找到最小一条边，权值为1，判断结点2和3不在一个集合中，将结点2和3并到一个集合中 。集合状态为：{2,3}

找到第二小的边，权值为2，判断0和1不在一个集合中，将0和1并集。集合状态为：{2,3} ， {0,1}

找到第三小的边，权值为2，判断0和3不在一个集合中，则将0和3并集。集合状态为：{0,1,2,3}

找到第四小的边，权值为3，发现1和2在一个集合里，则舍弃，同理第五小的边也舍弃。

完整代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 10000;
struct edge{int u,v,cost; 
};/*按edge.cost的顺序从小到大排列*/
bool cmp(const edge& e1, const edge& e2)
{return e1.cost < e2.cost; 
}
edge es[maxn];
int V,E;
int par[maxn];/*建图*/
void build()
{scanf("%d%d",&V,&E);for(int i=0; i<E; i++){scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost);}return;
}/*初始化并查集*/ 
void init_union_find(int V)
{for(int i=0 ;i<V; i++){par[i] = i;}return;
}/*找爹*/
int find(int x)
{int r = x;while(r!=par[r])r = par[r];int i = x;int j;while(i!=r){j = par[i];par[i] = r;i = j;} return r;
}/*判断是否有同一个爹*/
int same(int x, int y)
{return find(x)==find(y);
}/*将集合合并*/ 
void unite(int x, int y)
{if(same(x,y)){return;}else{par[find(x)] = find(y);}
}int kruskal()
{sort(es, es+E, cmp);init_union_find(V);int res = 0;for(int i=0; i<E; i++){edge e = es[i];if(!same(e.u, e.v)){unite(e.u, e.v);res += e.cost;}}return res;
} 
int main()
{build();printf("%d",kruskal());return 0; 
}

运行图：