我写了个最小生成树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 编辑 ]

按长度排序有问题吧

 Qsort(start,end,length,0,m-1); 在调用这函数后 你输出值看看
    printf("\n");
    for(i=0; i<m; ++i )
        printf("%d %d %d\n",start[i],end[i],length[i]);

刚看错了  排序没问题  你只是在合并集合的时候错了 就那么一个错误 呵呵
#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[i]);
        y=find(end[i]);
        if(x!=y)
        {
            ans=ans+length[i];
            dis[x]=y;//用dis一个集合就可以  不然你找结点的父结点的时候他们永远也不会在一个集合中
        }
    }
    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;
}


还有快排为什么不直接调用QSORT函数呢？ 不过很佩服自己写快排的 呵呵
还有 这次为什么没分了啊

收到的鲜花

• sunyh1999 于 2011-04-03 16:19 送鲜花  49朵   附言：好文章

我上午的时候已经解决这个合并问题了。。。

不过谢谢啊，我可以将分给你