0

我有两个 Kruskal 算法实现。一个是我做的，另一个是我从朋友那里拿的。这两个程序在我看来几乎相同，除了一些无关紧要的事情。

他的程序给出的输出与我的不同，尽管我认为他们都给出了错误的边集但正确的权重。

我的程序：

#include<stdio.h>
#include<stdlib.h>

typedef struct info
{
    int initial;
    int final;
    int weight;
}info;

void uon(int x,int y,int*p,int *r);
int findset(int x,int *p);
void sort(info *edgelist,int n);
void qksort(info *edgelist,int l,int u);
int partition(info *edgelist,int l,int u);
void makeset(int n,int *p,int *r);
int kruskal(info *edgelist,int n,int w);

int main()
{

    FILE *fp;
    int n,i,j,temp;
    int **gmatrix,cost;
    info *edgelist;
    int cnt =0,a;
    fp = fopen("grph.txt","r");

    fscanf(fp,"%d",&n);

    gmatrix=(int**)calloc(sizeof(int*),n);

    for(i=0;i<n;i++)
        gmatrix[i]=(int*)calloc(sizeof(int),n);

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            fscanf(fp,"%d",&temp);
            gmatrix[i][j]=temp;
        }
    }

    edgelist = (info*)calloc(sizeof(info),n*n);

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("%d  ",gmatrix[i][j]);
            temp = gmatrix[i][j];
            a=cnt;
            if(temp !=0)
            {
                edgelist[a].initial = i;
                edgelist[a].weight = temp;
                edgelist[a].final = j;
                cnt++;
            }

        }
        printf("\n");
    }
    printf("%d \n",edgelist[0].initial);
    printf("%d \n ",cnt);

    cost =kruskal(edgelist,n,cnt);
    printf("\nTotal Cost is %d",cost);

    return 0;
}

int kruskal(info *edgelist,int n,int cnt)
{
    int b,i,initial,dest,cost_cnt=0;
    int *p,*r;
    int cost=0;
    info *krus;

    p = (int*)calloc(sizeof(int),n);
    r = (int*)calloc(sizeof(int),n);

    makeset(n,p,r);
    qksort(edgelist,0,cnt);
    //sort(edgelist,w);

    krus=(info*)calloc(sizeof(info),n-1);
    for(i=0;i<cnt;i++)
    {
        //printf("INITIAL 1 : %d \n",edgelist[i].initial);
        initial=findset(edgelist[i].initial,p);
    //  printf("INITIAL 2 : %d \n",initial);
        dest=findset(edgelist[i].final,p);

        if(initial!=dest)
        {
            b=cost_cnt; 
            krus[b].initial=initial;
            krus[b].final=dest;
            krus[b].weight=edgelist[i].weight;
            cost_cnt++;
            uon(initial,dest,p,r);
        }

    }
        for(i=0;i<cost_cnt;i++)
        {
            printf("{%d,%d}: %d \n",krus[i].initial+1,krus[i].final+1, krus[i].weight);
            cost = cost + krus[i].weight;
        }
    return cost;

}

void uon(int initial,int dest,int *p,int *r)
{
    int u,v;
    //link(findset(x),findset(y));
    printf("\n X1 : %d",initial);
    u = findset(initial,p);
    printf("\n X2 : %d",initial);
    v = findset(dest,p);
    if(r[u]>r[v])
    {
        p[v] = u;
    }
    else
    {
        p[u] = v;

        if(r[u]==r[v])
            r[v] = r[v]+1;
    }
}


int findset(int x,int *p)
{
    if(x!=p[x])
    {

        p[x]=findset(p[x],p);
    }
    return p[x];
}
void makeset(int n,int *p,int *r)
{
    int i;
    for(i=0;i<n;i++)
    {
        p[i] = i;
        r[i] = 0;
    }
}



void qksort(info *edgelist,int l,int u) {
    int pq;
    if(l<u) 
    {
        pq=partition(edgelist,l,u);
        qksort(edgelist,l,pq-1);
        qksort(edgelist,pq+1,u);
    }
}

int partition(info *edgelist,int l,int u) {
    int i,j,pq;
    info pv,t;
    pv.initial=edgelist[l].initial;
    pv.final=edgelist[l].final;
    pv.weight=edgelist[l].weight;
    j=l;
    for(i=l+1;i<=u;i++)
    {
        if(edgelist[i].weight<=pv.weight) 
        {
            j++;
            t=edgelist[i];

            t.initial=edgelist[i].initial;
            t.final=edgelist[i].final;
            t.weight=edgelist[i].weight;

            edgelist[i].initial=edgelist[j].initial;
            edgelist[i].final=edgelist[j].final;
            edgelist[i].weight=edgelist[j].weight;

            edgelist[j].initial=t.initial;
            edgelist[j].final=t.final;
            edgelist[j].weight=t.weight;
        }
    }
    pq=j;

    t.initial=edgelist[pq].initial;
    t.final=edgelist[pq].final;
    t.weight=edgelist[pq].weight;

    edgelist[pq].initial=edgelist[l].initial;
    edgelist[pq].final=edgelist[l].final;
    edgelist[pq].weight=edgelist[l].weight;

    edgelist[l].initial=t.initial;
    edgelist[l].final=t.final;
    edgelist[l].weight=t.weight;

    return(pq);
}

朋友计划：

#include<stdio.h>
#include<stdlib.h>

struct info{
    int initial;
    int dest;
    int weight;
};
void kruskal(struct info *,int **,int,int);
void makeset(int *,int *,int);
void quick_sort(struct info *,int,int);
int find_set(int *,int);
void union_set(int * ,int *,int,int);
int partition(struct info *,int,int);

int main(int argc,char **argv)
{
    FILE *fp;
    int **gmatrix;
    int num,source,i,j,temp,count,a;
    struct info *edgelist;
    if(argc!=2)
    {
        printf("enter the proper argument");
        return(EXIT_FAILURE);
    }
    fp=fopen(argv[1],"r");
    fscanf(fp,"%d",&num);
    printf("num=%d\n",num);
    gmatrix=(int **)calloc(sizeof(int *),num);

    for(i=0;i<num;i++)
        gmatrix[i]=(int *)calloc(sizeof(int),num);

    for(i=0;i<num;i++)
    {
        for(j=0;j<num;j++)
        {
            fscanf(fp,"%d",&temp);
            *(*(gmatrix+i)+j)=temp;
        }
    }
    edgelist=(struct info *)calloc(sizeof(struct info),num*num);

    count=0;
    for(i=0;i<num;i++)
    {
        for(j=0;j<num;j++)
        {
            temp=*(*(gmatrix+i)+j);
            if(temp!=0)
            {

                a=count;            
                edgelist[a].initial=i;
                edgelist[a].dest=j;
                printf("(%d,%d)\n",edgelist[a].initial,edgelist[a].dest);
                edgelist[a].weight=temp;
                printf("weight=%d\t",edgelist[a].weight);

                count=count+1;
                printf("a=%d\n",count);
            }
        }
    }

    printf("ans=%d\t",count);
    kruskal(edgelist,gmatrix,num,count);
}

void kruskal(struct info *edgelist,int **gmatrix,int num,int count)
{

    int *parent;
    int *rank;
    int i,cost_count,b,initial,dest,cost=0;
    struct info *krus;  
    parent = (int *)calloc(sizeof(int),num);
    rank   = (int *)calloc(sizeof(int),num);

    makeset(parent,rank,num);
    quick_sort(edgelist,0,count);
    for(i=0;i<count;i++)
    {
        printf("sorting=%d\t",edgelist[i].weight);
    }

    krus=(struct info *)calloc(sizeof(struct info),num-1);
    cost_count=0;
    for(i=0;i<count;i++)
    {
        initial=find_set(parent,edgelist[i].initial);
        dest=find_set(parent,edgelist[i].dest);

        if(initial != dest )
        {
            b=cost_count;
            krus[b].initial=initial;
            krus[b].dest=dest;
            krus[b].weight=edgelist[i].weight;
            cost_count=cost_count+1;
    //      printf("weight=%d and (%d,%d)\t",krus[b].weight,krus[b].initial,krus[b].dest);
            union_set(parent,rank,initial,dest);
        }

    }

        for (i=0;i<num-1;i++) {
        printf("\n%d . {%d, %d}",i+1,krus[i].initial+1,krus[i].dest+1);
        cost = cost + krus[i].weight;
        }

    printf("\ncost of minimum mst is..... %d\n\n",cost);

}



void union_set(int *parent ,int *rank,int initial,int dest)
{
    int u,v;
    printf("\n X1 : %d",u);
    u=find_set(parent,initial);
    printf("\n X2 : %d\n",u);
    v=find_set(parent,dest);
    if(rank[u]>rank[v])
        parent[v]=u;
    else    
    {
        parent[u]=v;
        if(rank[u]==rank[v])
        rank[v]=rank[v]+1;
    }
}
int find_set(int *parent,int x)
{
    if(x!=parent[x])
        parent[x] = find_set(parent,parent[x]);
    return parent[x];
}
void makeset(int *parent,int *rank,int num)
{
    int i;
    for (i=0; i<num; i++) 
    {
        parent[i] = i;
        rank[i]   = 0;
    }
}
void quick_sort(struct info *edgelist,int left,int right)
{
    int q;
    if(left<right)
    {
        q=partition(edgelist,left,right);
        quick_sort(edgelist,left,q-1);
        quick_sort(edgelist,q+1,right);
    }
}
int partition(struct info *edgelist,int left,int right)
{
    struct info pivot,temp;
    int i,j,k,pp;

    pivot.initial=edgelist[left].initial;
    pivot.dest   =edgelist[left].dest;
    pivot.weight =edgelist[left].weight;

    j=left;


    for(i=left+1;i<=right;i++)
    {
        if(edgelist[i].weight < pivot.weight)
        {
        j=j+1;

        temp.initial=edgelist[i].initial;
        temp.dest=edgelist[i].dest;
        temp.weight=edgelist[i].weight;

        edgelist[i].initial=edgelist[j].initial;
        edgelist[i].dest=edgelist[j].dest;
        edgelist[i].weight=edgelist[j].weight;

        edgelist[j].initial=temp.initial;
        edgelist[j].dest=temp.dest;
        edgelist[j].weight=temp.weight;
        }
    }
    pp=j;

    temp.initial=edgelist[left].initial;
    temp.dest=edgelist[left].dest;
    temp.weight=edgelist[left].weight;

    edgelist[left].initial=edgelist[pp].initial;
    edgelist[left].dest=edgelist[pp].dest;
    edgelist[left].weight=edgelist[pp].weight;

    edgelist[pp].initial=temp.initial;
    edgelist[pp].dest=temp.dest;
    edgelist[pp].weight=temp.weight;

        //printf("aaaa=%d\t\n",pp);

    return pp;
}

我正在使用的图表：

9
0 4 0 0 0 0 0 8 0
4 0 8 0 0 0 0 11 0
0 8 0 7 0 4 0 0 2
0 0 7 0 9 14 0 0 0
0 0 0 9 0 10 0 0 0
0 0 4 14 10 0 2 0 0
0 0 0 0 0 2 0 1 6
8 11 0 0 0 0 1 0 7
0 0 2 0 0 0 6 7 0

权重是 37，但程序没有给出正确的边集。

4

2 回答 2

1

排序顺序

代码之间的区别在于，在快速排序例程中，一个代码使用：

if(edgelist[i].weight<=pv.weight)

而其他用途

if(edgelist[i].weight < pivot.weight)

这导致边缘呈现的不同顺序。

两种解决方案都在计算有效但不同的最小生成树。

边缘显示

但是，由于代码的原因，两种解决方案中所选边的最终显示都不正确：

krus[b].initial=initial;
krus[b].final=dest;

它在初始和目标变量通过 findset 例程后存储它们。这应该替换为：

krus[b].initial=edgelist[i].initial
krus[b].final=edgelist[i].final

附言

顺便说一句，两种解决方案也共享调用的错误

 qksort(edgelist,0,cnt);

代替

 qksort(edgelist,0,cnt-1);

但这对输出没有任何影响。（所发生的一切是第一个呈现的边看起来像是从 0 开始和结束，所以被忽略了。）

于 2013-09-11T20:04:19.363 回答
0

显然，打印的权重与节点编号不对应，因此如果解析和打印正常，则节点信息在某处损坏。

快速排序实现看起来不错，唯一修改节点信息的地方是kruskal()函数。

所以，提示：仔细检查分配给krus[b].initial. 真的initial是 edge 的初始节点号i吗？

于 2013-09-12T02:31:31.510 回答