-1
我已经制定了一个程序来实现prim的算法，但它并不像它应该那样工作。 顶点在优先级队列上得到改变，一个顶点甚至不改变它的权重和父级。MST - Prims算法使用C
的代码是
#include<stdio.h>
#include<stdlib.h>
typedef struct info
{
int parent;
int vertex;
int weight;
}info;
typedef struct alist
{
int vertex;
int weight;
struct alist *next;
}alist;
int prims(info *vertexlist,alist **adjlist,int n);
void minheapify(info *A,int heapsize,int index);
void buildminheap(info *A, int heapsize);
void heapdecreasekey(info *A,int w,int index);
info extractmin(info *A,int heapsize);
int main()
{
FILE *fp;
int n,i,j,temp;
int **gmatrix,cost;
info *vertexlist;
alist **adjlist,*head,*newnode,*tail,*v;
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;
}
}
vertexlist = (info*)calloc(sizeof(info),n);
adjlist = (alist**)calloc(sizeof(alist),n);
for(i=0;i<n;i++)
{
vertexlist[i].parent=(-10);
vertexlist[i].weight = 32767;
vertexlist[i].vertex= i;
head=NULL;
for(j=0;j<n;j++)
{
printf("%d ",gmatrix[i][j]);
temp = gmatrix[i][j];
if(temp!=0)
{
newnode=(alist*)malloc(sizeof(alist));
newnode->next=NULL;
newnode->vertex=j;
newnode->weight=temp;
if(head==NULL)
head=newnode;
else
tail->next=newnode;
tail=newnode;
}
}
adjlist[i]=head;
printf("\n");
}
cost=prims(vertexlist,adjlist,n);
printf("The adjacency list is :\n");
for(i=0;i<n;i++)
{
printf("%d :",i+1);
v=adjlist[i];
while(v!=NULL)
{
printf("%d->",v->vertex+1);
v=v->next;
}
printf("\n");
}
printf("The Vertex Pairs are: \n");
for(i=0;i<n;i++)
{
if(vertexlist[i].parent>-999)
{
printf("(%d,%d) : %d \n",vertexlist[i].parent+1,vertexlist[i].vertex+1,vertexlist[i].weight);
cost=cost+vertexlist[i].weight;
}
}
printf("\nTotal Cost is %d",cost);
return 0;
}
int prims(info *vertexlist,alist **adjlist,int n)
{
int index,heapsize,i;
info u;
alist *v;
vertexlist[0].weight=0;
//vertexlist[0].parent=0;
buildminheap(vertexlist,n);
heapsize=n;
while(heapsize!=1)
{
u=extractmin(vertexlist,heapsize);
heapsize--;
index=u.vertex;
v=adjlist[index];
while(v!=NULL)
{
for(i=0;i<heapsize;i++)
{
if(vertexlist[i].vertex==v->vertex && v->weight<vertexlist[i].weight)
{
vertexlist[i].parent=index;
heapdecreasekey(vertexlist,v->weight,i);
}
}
v=v->next;
}
}
return 0;
}
info extractmin(info *A,int heapsize)
{
info u;
int a;
u=A[0];
if(heapsize!=1)
{
A[0]=A[(heapsize-1)];
A[(heapsize-1)]=u;
heapsize=heapsize-1;
minheapify(A,heapsize,1);
}
return u;
}
void heapdecreasekey(info *A,int w,int i)
{
int j;
info t;
j = (i-1)/2;
A[i].weight=w;
while((i>0) && A[(i-1)/2].weight>A[i].weight)
{
t=A[i];
A[i]=A[(i-1)/2];
A[(i-1)/2] = t;
i= (i-1)/2;
}
}
void buildminheap(info *A, int heapsize)
{
int i;
for(i=(heapsize-1)/2;i>=0;i--)
{
minheapify(A,heapsize,i);
}
}
void minheapify(info *A,int heapsize,int index)
{
info temp;
int left,right,smallest;
left = (2*index)+1;
right = (2*index)+2;
if((left<heapsize) && (A[index].weight>A[left].weight))
{
smallest=left;
}
else
smallest=index;
if((right<heapsize) && (A[smallest].weight>A[right].weight))
{
smallest=right;
}
if(smallest!=index)
{
temp=A[smallest];
A[smallest] = A[index];
A[index]=temp;
minheapify(A,heapsize,smallest);
}
}
输出是：
F:\cse75>gcc prims.c
F:\cse75>a
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
The adjacency list is :
1 :2->8->
2 :1->3->8->
3 :2->4->6->9->
4 :3->5->6->
5 :4->6->
6 :3->4->5->7->
7 :6->8->9->
8 :1->2->7->9->
9 :3->7->8->
The Vertex Pairs are:
(7,6) : 2
(3,4) : 7
(-9,5) : 32767
(7,8) : 1
(9,7) : 6
(3,9) : 2
(2,3) : 8
(1,2) : 4
(-9,1) : 0
Total Cost is 32797
虽然从我正确的MST克鲁斯卡算法的输出是
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
The edges and weights are :
{7,8}: 1
{7,6}: 2
{3,9}: 2
{6,3}: 4
{2,1}: 4
{4,3}: 7
{2,3}: 8
{5,4}: 9
Total Cost is 37
在评估的代码，我发现，该堆不能正常工作，因为它应该是。当顶点5被提取时，它的权重是4并且父母是-10，这不应该发生，就好像权重减少了一样，应该有父母。在那一点上，其他顶点与相应的父母有不正确的权重。
index :8
5:vertex: 5 weight: 4 parent: -9
6:vertex: 6 weight: 5 parent: 7
4:vertex: 4 weight: 3 parent: 3
编辑： 这个问题似乎是在heapdecrease function.Because如果我通过邻接表遍历后调用buildminheap。然后我得到正确的结果。 虽然堆积函数对我而言是正确的，但这是错误的。
'完全怪异的 - - 你需要澄清。预期产出是多少，你得到了什么？你不能指望人们阅读你的所有代码并自己理解问题。 –
我更新了这个帖子 –