MST - Алгоритм Prims с использованием C

Question

Я разработал программу для реализации алгоритма примитивов, но он не работает так, как должно быть. Вершины изменяются в очереди приоритетов, одна вершина даже не меняет свой вес и родительский.

Код

#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, а parent - -10, что не должно происходить, как если бы вес уменьшался, должен быть родитель. И в этот момент другие вершины имеют неправильные веса с соответствующими родителями.

index :8 
5:vertex: 5 weight: 4 parent: -9 
6:vertex: 6 weight: 5 parent: 7 
4:vertex: 4 weight: 3 parent: 3 

EDIT: Проблема, кажется, в heapdecrease function.Because, если я называю buildminheap после прохождения через список смежности. Тогда я получаю правильный результат. Хотя функция heapdecrease верна мне, это неправильно.

Answer 1

В качестве стартера вы не инициализируете head и tail.

Далее, в цикле над списком смежности условие должно быть v != NULL или иначе вы пропустите первый исходящий край.

В extractmin вы действительно хотите сохранить извлеченный элемент в массиве, потому что после вызова prim внутри 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 

И при отображении дерева, не отображается, если ребро parent - -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; 
    }