Prim’s Algorithm in C [Program & Algorithm]

Here you will find out about Prims’s calculation in C with a program model.

Tidy’s Algorithm is a way to deal with decide least cost spreading over the tree. For this situation, we start with a single edge of the chart and we add edges to it lastly we get a least-cost tree.

For this situation, too, we have n-1 edges when a number of hubs in the diagram are n. We over and over add edges to tree and tree is stretched out to make crossing tree, while if there should be an occurrence of Kruskal’s calculation there might be more than one tree, which is at last associated through the edge to make spreading over the tree.

Calculation

This calculation makes spreading over the tree with the least weight from a given weighted diagram.

Start

Make edge rundown of the given diagram, with their loads.

Attract all hubs to make a skeleton for crossing tree.

Select an edge with most reduced weight and add it to the skeleton and erase edge from edge list.

Include different edges. While including an edge take care that the one finish of the edge ought to consistently be in the skeleton tree and its expense ought to be least.

Rehash stage 5 until n-1 edges are included.

Return.

Program for Prim’s Algorithm in C

C program for building a base expense spreading over the tree of a chart utilizing Prim’s calculation is given underneath.

#include<stdio.h>
#include<stdlib.h>
 
#define infinity 9999
#define MAX 20
 
int G[MAX][MAX],spanning[MAX][MAX],n;
 
int prims();
 
int main()
{
	int i,j,total_cost;
	printf("Enter no. of vertices:");
	scanf("%d",&n);
	
	printf("\nEnter the adjacency matrix:\n");
	
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&G[i][j]);
	
	total_cost=prims();
	printf("\nspanning tree matrix:\n");
	
	for(i=0;i<n;i++)
	{
		printf("\n");
		for(j=0;j<n;j++)
			printf("%d\t",spanning[i][j]);
	}
	
	printf("\n\nTotal cost of spanning tree=%d",total_cost);
	return 0;
}
 
int prims()
{
	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;
		}
		
	//initialise 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);
}

Output

Enter no. of vertices:6

Enter the adjacency matrix:
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

spanning tree matrix:

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

Time Complexity

Tidy’s calculation contains two settled circles. Every one of this circle has a multifaceted nature of O (n). In this manner, the unpredictability of Prim’s calculation for a diagram having n vertices = O (n2).

Remark beneath on the off chance that you discovered anything wrong or missing in over tidy’s calculation in C.