Question

求最小生成树的kruska算法，效率尽量高，尽量多点注释！c++代码

Answer 1

/*
基本算法思想：
为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。
具体作法如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。
由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选。

用并查积 和 克鲁是卡尔算法实现查找最短边
利用快排按边递增排列，每次从中选出最短边,同时将最短边的两个顶点并入到集合中
心得：利用并查积 和 kruskal算法结合找最短路径可以使查找的效率更高
加入集合中的边都是构成最小生成树的边，所以每家一次sum 都要加上这两个顶点之间的距离
*/
/*下面的代码输入n个节点，然后输入n*（n-1）/2条边及权值，输出是连通这些边的最小权值*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

struct ed
{
int u; //起始点
int v; //终结点
int w; //权重
};
bool cmp(ed a,ed b)
{
return a.w<b.w; //从小到大排序
}
struct ed edge[100000];
int p[105];

int find(int x) //查找x的父亲
{
while(p[x]!=x)
x=p[x];
return x;
}
int kruskal(int n)
{
int i,count=1,sum=0;
for(i=0;i<=n;i++)
p[i]=i; //并查集初始化，每个节点到父亲是自己
int x,y;
sort(edge,edge+n*(n-1)/2,cmp); //快速排序
for(i=0;count<n;i++)
{
x=find(edge[i].u); //点edge[i].u的父亲是x
y=find(edge[i].v); //点edge[i].v的父亲是y
if(x!=y) //判断是否会路
{
count++; //加上一条边
p[x]=y; //把x和y加入统一个集合
sum+=edge[i].w;
}
}
return sum;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n) //输入n个节点
{
int i;
for(i=0;i<n*(n-1)/2;i++) //输入 n*（n-1）/2条边
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); //表示点edge[i].u和点edge[i].v之间的权重为 edge[i].w
printf("%d\n",kruskal(n));
}
return 0;
}

楼主，这可是本人一个字一个字敲出来点，要给分啊

Answer 2

B.Kruskal算法：(贪心)

按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v:integer):integer; {返回顶点v所在的集合}
var i:integer;
begin
i:=1;
while (i<=n) and (not v in vset[i]) do inc(i);
if i<=n then find:=i else find:=0;
end;

procedure kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset[i]:=[i];{初始化定义n个集合，第I个集合包含一个元素I}
p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针}
sort;
{对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}
while p>0 do begin
i:=find(e[q].v1);j:=find(e[q].v2);
if i<>j then begin
inc(tot,e[q].len);
vset[i]:=vset[i]+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
我找的,CSDN算法大全.TXT

Answer 3

#include <stdio.h>

typedef struct node
{
int x,y,length;
};

node list[500001];
int father[500001];
int n,m,total;
int ans;

int get_father(int k,int father[])
{
int fath=k;
int x;
while (father[fath]!=fath)
{
fath=father[fath];
}
while (father[k]!=k)
{
x=k;
k=father[k];
father[x]=fath;
}
return fath;
}//路径压缩

void add(int x,int y,int father[])
{
x=get_father(x,father);
y=get_father(y,father);
father[x]=y;
}//集合合并

bool judge(int x,int y,int father[])
{
return get_father(x,father)==get_father(y,father);
}//判断是否同一集合

void change(node &a,node &b)
{
node h=a;
a=b;
b=h;
}

void qsort(int x,int y,node list[])
{
if (x>=y) return ;
int p=x-1,q=y+1;
int mid=list[(x+y)/2].length;
do
{
p++;q--;
while (list[p].length<mid) p++;
while (list[q].length>mid) q--;
if (p<q) change(list[p],list[q]);
}while (p<q);
qsort(x,q,list);qsort(q+1,y,list);
}

int main(void)
{
int i;
while (scanf("%d %d",&n,&m)==2)
{
for (i=1;i<=m;i++)
scanf("%d %d %d",&list[i].x,&list[i].y,&list[i].length);
qsort(1,m,list);
for (i=1;i<=n;i++) father[i]=i;//并查集初始化
total=0;//总的已经选取的点数
ans=-1;
for (i=1;i<=m;i++)
{
if (!judge(list[i].x,list[i].y,father))
{
add(list[i].x,list[i].y,father);
if (list[i].length>ans) ans=list[i].length;//这里选取最小生成树最长的路径。如要统计总的代价，让前面的ans=0;这里改成 ans+=list[i].length;即可
total++;
}
if (total==n-1) break;
}
printf("%d\n",ans);
}
//while (1);
return 0;
}