算法概述:一个带权的连通图, 有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++;
}
}