8960 - Prim's Algorithm (MST).c

/**********************************************************************************************************
NAME: CANDIDA RUTH NORONHA
CLASS: SE COMPS B
ROLL NO. : 8960
BATCH: C
TITLE: PRIM'S ALGORITHM - MINIMUM SPANNING TREE
SUBMISSION DATE : 25th MARCH, 2021
**********************************************************************************************************/

#include<stdio.h>
#include<stdlib.h>

#define infinity 9999
#define MAX 20

int prims(int G[MAX][MAX],int spanning[MAX][MAX],int n)
{
	int cost[MAX][MAX];
	int u,v,min_distance,distance[MAX],from[MAX];
	int visited[MAX],no_of_edges,i,min_cost,j;


	//create cost[][] matrix,spanning[][]
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			if(G[i][j]==0)
				cost[i][j]=infinity;
			else
				cost[i][j]=G[i][j];
				spanning[i][j]=0;
		}

	//initialize visited[],distance[] and from[]
	distance[0]=0;
	visited[0]=1;

	for(i=1;i<n;i++)
	{
		distance[i]=cost[0][i];
		from[i]=0;
		visited[i]=0;
	}

	min_cost=0;		//cost of spanning tree
	no_of_edges=n-1;		//no. of edges to be added

	while(no_of_edges>0)
	{
		//find the vertex at minimum distance from the tree
		min_distance=infinity;
		for(i=1;i<n;i++)
			if(visited[i]==0&&distance[i]<min_distance)
			{
				v=i;
				min_distance=distance[i];
			}

		u=from[v];

		//insert the edge in spanning tree
		spanning[u][v]=distance[v];
		spanning[v][u]=distance[v];
		no_of_edges--;
		visited[v]=1;

		//updated the distance[] array
		for(i=1;i<n;i++)
			if(visited[i]==0&&cost[i][v]<distance[i])
			{
				distance[i]=cost[i][v];
				from[i]=v;
			}

		min_cost=min_cost+cost[u][v];
	}

	return(min_cost);
}

int main()
{
	int i,j,total_cost;
	int G[MAX][MAX],spanning[MAX][MAX],n;
	printf("\n------------------------------------------------------------------------------------------------\n");
	printf(" Enter the number of nodes in the Graph : ");
	scanf("%d",&n);

	printf("\n------------------------------------------------------------------------------------------------\n");
	printf("\n Enter the adjacency matrix of the Graph : \n");

	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&G[i][j]);
    printf("\n------------------------------------------------------------------------------------------------\n");

	total_cost=prims(G,spanning,n);
	printf("\n The Minimum Spanning Tree Matrix is : \n");

	for(i=0;i<n;i++)
	{
		printf("\n");
		for(j=0;j<n;j++)
			printf("%d\t",spanning[i][j]);
	}
    printf("\n\n------------------------------------------------------------------------------------------------\n");
	printf("\n Total cost of spanning tree = %d",total_cost);
	printf("\n------------------------------------------------------------------------------------------------\n");
	return 0;
}

/**********************************************************************************************************

 OUTPUT :

------------------------------------------------------------------------------------------------
 Enter the number of nodes in the Graph : 6

------------------------------------------------------------------------------------------------

 Enter the adjacency matrix of the Graph :
0 3 1 6 0 0
3 0 5 0 3 0
1 5 0 5 6 4
6 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0

------------------------------------------------------------------------------------------------

 The Minimum Spanning Tree Matrix is :

0       3       1       0       0       0
3       0       0       0       3       0
1       0       0       0       0       4
0       0       0       0       0       2
0       3       0       0       0       0
0       0       4       2       0       0

------------------------------------------------------------------------------------------------

 Total cost of spanning tree = 13
------------------------------------------------------------------------------------------------

**********************************************************************************************************/