MST - Prims Algorithm using C

Question

I have made a program to implement prims' algorithm but it isnt working as it should be. The vertexes are getting changed on the priority queue, one vertex doesnt even change its weight and parent.

The code is

#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);
    }
}

The output is:

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

While the Output from my correct MST Kruskal Algorithm is

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

While evaluating the code, i found that the heap isn't working properly as it should be. When the vertex 5 is extracted its weight is 4 and parent is -10, which shouldnt happen as if weight is decreased there should be a parent. And at that point other vertices have wrong weights with corresponding parents.

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

EDIT: The problem seems to be in heapdecrease function.Because if i call buildminheap after traversing through the adjacency list. Then i get the correct result. Though the heapdecrease function is correct to my knowledge, it is wrong.

Answer 1

As a starter, you don't initialize head and tail.

Next, in the loop over adjacency list the condition should be v != NULL or otherwise you miss the first outgoing edge.

In extractmin you really want to keep the extracted element in the array, because after the invocation of prim inside main you access the whole vertexlist. So when extracting, simply copy the element at the end - it won't mess with the heap, because heapsize will be less then its index.

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;
}

When initializing the tree root, don't set the parent to a valid index, leave it to -10

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

And when displaying the tree, don't display an edge if the parent is -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;
    }