Lab program10: Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm

Description:

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Algorithm

1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
3. Repeat step 2 (until all vertices are in the tree).

Solution:

# include <stdio.h>

int Prim (int g[20][20], int n, int t[20][20])

{

            int u,v, min, mincost;

            int visited[20];

            int i,j,k;

            visited[1] = 1;

            for(k=2; k<=n; k++)

            visited[k] = 0 ;

            mincost = 0;

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

            {

                        min= 99;

                        u=1;

                        v=1;

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

                                    if(visited[i]==1)

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

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

                                                            {

                                                                        min = g[i][j];

                                                                        u = i;    v = j;

                                                            }

                        t[u][v] = t[v][u] = g[u][v] ;

                        mincost = mincost + g[u][v] ;

                        visited[v] = 1;

                        printf("\n (%d, %d) = %d", u, v, t[u][v]);

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

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

                        if( visited[i] && visited[j] )

                        g[i][j] = g[j][i] = 99;

            }

            return(mincost);

}

void main()

{

            int n, cost[20][20], t[20][20];

            int mincost,i,j;

           

printf("\nEnter the no of nodes: ");

            scanf("%d",&n);

           

printf("Enter the cost matrix:\n");

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

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

             {

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

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

                        cost[i][j]=99;

             }

           

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

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

           

                        t[i][j] = 99;

            printf("\nThe order of Insertion of edges:");

            mincost = Prim (cost,n,t);

            printf("\nMinimum cost = %d\n\n", mincost);

}

OUTPUT 1 :

Enter How many nodes : 5

enter the cost matrix

0 11 9  7   8

11 0 15 14 13

9 15 0 12  14

7 14 12 0  6

8 13 14 6  0

The order of Insertion of edges :

 (1, 4) = 7

 (4, 5) = 6

 (1, 3) = 9

 (1, 2) = 11

 Minimum cost = 33

OUTPUT  2:

enter How many nodes : 3

enter the cost matrix

0 6 1

6 0 10

1 10 0

 The order of Insertion of edges :

 (1, 3) = 1

 (1, 2) = 6

 Minimum cost = 7