-1

我已经编写了一个程序来实现 prims 的算法，但它没有按应有的方式工作。优先级队列上的顶点正在发生变化，一个顶点甚至没有改变它的权重和父级。

代码是

#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 Kruskal 算法的输出是

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 函数中。因为如果我在遍历邻接列表后调用 buildminheap。然后我得到正确的结果。尽管据我所知 heapdecrease 函数是正确的，但它是错误的。

4

1 回答 1

1

作为初学者，您不需要初始化head和tail.

接下来，在邻接列表的循环中，条件应该是v != NULL ，否则您会错过第一个传出边。

在extractmin您确实希望将提取的元素保留在数组中，因为在调用priminside之后main您可以访问整个vertexlist. 因此，在提取时，只需在最后复制元素 - 它不会弄乱堆，因为heapsize它会小于它的索引。

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; // ADDED THIS LINE
      heapsize = heapsize - 1;
      minheapify (A, heapsize, 0); // HERE MUST START from 0, not 1
    } 
  return u;
}

初始化树根时，不要将父级设置为有效索引，将其保留为 -10

//   vertexlist[5].parent = 0; COMMENTED OUT

并且在显示树时，如果父级为-10，则不显示边缘。

  if (vertexlist[i].parent >= 0) // ADDED THIS LINE
    {
      printf ("(%d,%d) : %d \n", vertexlist[i].parent + 1,
              vertexlist[i].vertex + 1, vertexlist[i].weight);
      cost = cost + vertexlist[i].weight;
    }
于 2013-11-09T20:31:11.627 回答