Prim’s Algorithm

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected 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. This algorithm is directly based on the MST( minimum spanning tree) property.

Capture

Algorithm

MST-PRIM(G, w, r)
	for each u  V [G]
	do key[u] ← ∞
	π[u] ← NIL
	key[r] ← 0
	Q ← V [G]
	while Q ≠ Ø
		do u ← EXTRACT-MIN(Q)
			for each v  Adj[u]
				do if v  Q and w(u, v) < key[v]
					then π[v] ← u
						key[v] ← w(u, v)

Procedure

Step1

No. of Nodes        0        1        2        3        4        5
Distance        0        3        1        6        ∞        ∞
Distance From          0        0        0    
                    

Step2

No. of Nodes        0        1        2        3        4        5
Distance        0        3        0        5        6        4
Distance From          0          2        2        2
        

Step3

No. of Nodes        0        1        2        3        4        5
Distance        0        0        0        5        3        4
Distance From              2        1        2

Step4

No. of Nodes        0        1        2        3        4        5
Distance        0        0        0        5        0        4
Distance From              2          2

Step5

No. of Nodes        0        1        2        3        4        5
Distance        0        0        0        3        0        0
Distance From              2          2
Minimum Cost = 1+2+3+3+4 = 13

Implementation:

#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
	clrscr();
	printf("\nEnter the number of nodes:");
	scanf("%d",&n);
	printf("\nEnter the adjacency 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]=999;
	}
	visited[1]=1;
	printf("\n");
	while(ne < n)
	{
		for(i=1,min=999;i<=n;i++)
		for(j=1;j<=n;j++)
		if(cost[i][j]< min)
		if(visited[i]!=0)
		{
			min=cost[i][j];
			a=u=i;
			b=v=j;
		}
		if(visited[u]==0 || visited[v]==0)
		{
			printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
			mincost+=min;
			visited[b]=1;
		}
		cost[a][b]=cost[b][a]=999;
	}
	printf("\n Minimun cost=%d",mincost);
	getch();
}

Time complexity

Minimum edge weight data structure Time complexity (total)
adjacency matrix, searching O(|V|2)
binary heap and adjacency list O((|V| + |E|) log |V|) = O(|E| log |V|)
Fibonacci heap and adjacency list O(|E| + |V| log |V|)