-1

プリムのアルゴリズムを実装するプログラムを作成しましたが、正常に動作しません。頂点はプライオリティ キューで変更されています。1 つの頂点は重みと親を変更しません。

コードは

#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 Algorithm からの出力は

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 か、そうでない場合は最初の発信エッジを逃します。

inの呼び出し後に全体にアクセスするextractminため、抽出された要素を配列に保持する必要があります。したがって、抽出するときは、要素を最後にコピーするだけです。インデックスよりも小さくなるため、ヒープを台無しにすることはありません。primmainvertexlistheapsize

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 に答える