最小生成数kurskal
我写了个最小生成树kurskal算法，但是程序的好像有点问题，请各位高手帮我看看测试数据：
输入：
7 11
1 2 7
1 4 5
2 3 8
2 4 9
2 5 7
3 5 5
4 5 15
4 6 6
5 6 8
5 7 9
6 7 11
输出：
39
#include <stdio.h>
#include <stdlib.h>
int dis[100];
void Qsort(int start[],int end[],int length[],int startPos, int endPos)
{
int i,j,temp1,temp2,temp3;
temp1=start[startPos];
temp2=end[startPos];
temp3=length[startPos];
i=startPos,j=endPos;
while(i<j)
{
while(temp3<=length[j]&&i<j) j--;
start[i]=start[j];
end[i]=end[j];
length[i]=length[j];
while(temp3>=length[i]&&i<j)i++;
start[j]=start[i];
end[j]=end[i];
length[j]=length[i];
}
start[i]=temp1;
end[i]=temp2;
length[i]=temp3;
if(i-1>startPos) Qsort(start,end,length,startPos,i-1);
if(endPos>i+1)Qsort(start,end,length,i+1,endPos);
}
int find(int number)
{
return dis[number]==number?number:(dis[number]=find(dis[number]));
}
int kruskal(int start[],int end[],int length[],int n,int m)
{
int mark[100];
int i,x,y,weight,ans=0;
for(i=0;i<n;i++) dis[i]=i;//p
for(i=0;i<m;i++) mark[i]=i;//r
for(i=0;i<m;i++)
{
weight=mark[i];
x=find(start[weight]);
y=find(end[weight]);
if(x!=y)
{
ans=ans+length[weight];
mark[x]=y;
}
}
return ans;
}
int main()
{
int start[100],end[100],length[100];
int i,n,m,ans;
scanf("%d %d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d %d %d",&start[i],&end[i],&length[i]);
start[i]--;end[i]--;
}
Qsort(start,end,length,0,m-1);
ans=kruskal(start,end,length,n,m);
printf("%d\n",ans);
system("pause");
return 0;
}
[ 本帖最后由 sunyh1999 于 2011-4-3 10:23 编辑 ]
