我有两个 Kruskal 算法实现。一个是我做的，另一个是我从 friend 那里拿来的。这两个程序在我看来几乎相同，除了一些无关紧要的事情。
他的程序给出了与我的不同的输出，尽管我认为他们都给出了错误的边集但给出了正确的权重。
我的程序:
#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);
}
friend 计划:
#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，但程序没有给出正确的边集。
最佳答案
排序顺序
代码之间的区别在于，在快速排序例程中，一个代码使用:
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 开始和结束，所以被忽略了。)
关于c - 使用 C 的 Kruskal 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18749417/