DS (II) Assignment 5: Set A- b)

b) Write a C program for the Implementation of Prim’s Minimum spanning tree algorithm.

Solution: 

#include<stdio.h>

int main()

{

    int adj_mat[10][10],visited[10]={0},i,j,n,no_e=1,min,a,b,min_cost=0;

    printf("Enter number of nodes ");

    scanf("%d",&n);

    printf("Enter adj_mat in form of adjacency matrix\n");

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

    {

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

        {

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

            // adj_mat is 0 then initialize it by maximum value

            if(adj_mat[i][j]==0)

              adj_mat[i][j]=1000;

        }

    }

    

    // logic for finding minimum adj_mat spanning tree

    visited[1]=1; // visited first node

    while(no_e<n)

    {

        min=1000;

        // in each cycle find minimum adj_mat 

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

        {

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

            {

                if(adj_mat[i][j]<min)

                {

                    if(visited[i]!=0)

                    {

                        min=adj_mat[i][j];

                        a=i;

                        b=j;

                    }

                }

            }

        }

        //if node is not visited

        if(visited[b]==0)

        {

            printf("\n%d to %d  adj_mat=%d",a,b,min);

            min_cost=min_cost+min;

            no_e++;

        }

        visited[b]=1;

        // initialize with maximum value you can also use any other value

        adj_mat[a][b]=adj_mat[b][a]=1000; 

    }

    printf("\nminimum weight is %d",min_cost);

    return 0;

}