Write a program to find the minimum cost spanning tree using prim’s algorithm.

Name of the experiment:  Write a program to find the minimum cost spanning tree using prim’s algorithm.

Algorithm:

1          Algorithm Prim ( E, cost, n, t)

2          {

3                      Let (k,l) be an edge of minimum cost in E;

4                      mincost:= cost[k,l];

5                      t[1,1]:= k; t[1,2]:=l;

6                      for i:= 1  to  n  do

7                                  if ( cost[I,l] < cost[I,k]) then near[i]:=l;

8                                  else near[i]:=k;

9                      near[k]:= near[l]:= 0;

10                   for i:=2 to  n-1  do

11                   {

12                               Let j be an index such that near[j] ≠ 0 and

13                               cost[j, near[j]] is minimum;

14                               t[i,1]:= j; t[I,2]:= near [j];

15                               mincost:= mincost + cost[j,near[j]];

16                               near [j]:= 0;

17                               for k:= 1 to n do

18                                           if ((near [k] ≠ 0) and (cost[k, near[k]] > cost [k, j]))

19                                                       then near[k]: j;

20                   }

21                   return mincost;

22       }

Source Code:

#include<stdio.h>

#include<conio.h>

int n, cost[10][10];

void prim()

{

            int i,j,k,l,x,nr[10],temp,min_cost=0,tree[10][3];

            temp=cost[0][0];

            for(i=0;i < n;i++)

            {

                        for(j=0;j < n;j++)

                        {

                                    if(temp > cost[i][j])

                                    {

                                                temp=cost[i][j];

                                                k=i;

                                                l=j;

                                    }

                        }

            }

            tree[0][0]=k;

            tree[0][1]=l;

            tree[0][2]=temp;

            min_cost=temp;

           

            for(i=0;i< n;i++)

            {

                        if(cost[i][k]< cost[i][l])

                                    nr[i]=k;

                        else

                                    nr[i]=l;

            }

                        nr[k]=100;

            nr[l]=100;

            temp=99;

            for(i=1;i< n-1;i++)

            {

                        for(j=0;j< n;j++)

                        {

                           if(nr[j]!=100 && cost[j][nr[j]] < temp)

                           {

                                       temp=cost[j][nr[j]];

                                       x=j;

                           }

                        }

                        tree[i][0]=x;

                        tree[i][1]=nr[x];

                        tree[i][2]=cost[x][nr[x]];

                        min_cost=min_cost+cost[x][nr[x]];

                        nr[x]=100;

                        for(j=0;j< n;j++)

                        {

                                    if(nr[j]!=100 && cost[j][nr[j]] > cost[j][x])

                                                nr[j]=x;

                        }

                        temp=99;

            }

            printf("\n The min spanning tree is:- \n");

            for(i=0;i < n-1;i++)

            {

                        for(j=0;j < 3;j++)

                           printf("%d\t", tree[i][j]);

                        printf("\n");

            }

            printf("\n Min cost:- %d", min_cost);

}

void main()

{

            int i,j;

            printf("\n Enter the no. of vertices:- ");

            scanf("%d", &n);

            printf ("\n Enter the costs of edges in matrix form:- ");

            for(i=0;i< n;i++)

                        for(j=0;j< n;j++)

                                    scanf("%d",&cost[i][j]);

            printf("\n The matrix is:- \n");

            for(i=0;i< n;i++)

            {

                        for(j=0;j < n;j++)

                                    printf("%d\t",cost[i][j]);

                        printf("\n");

            }

            prim();

            getch();

}

Sample input and Output:

Enter the no. of vertices:-            3

Enter the costs of edges in matrix from:-

99   2   3

2   99   5

3   5   99 

The matrix is:-

99       2          3

2          99       5

3          5          99 

The min spanning tree is:-

0          1          2

2          0          3

Min cost:-     5