Prim's Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph.
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.

---

Example

A Simple Weighted Graph	Minimum-Cost Spanning Tree

---

Prim's Algorithm

MST-PRIM(G, w, r)

1.	for each u  V [G]

2.	do key[u] ← ∞

3.	π[u] ← NIL

4.	key[r] ← 0

5.	Q ← V [G]

6.	while Q ≠ Ø

7.		do u ← EXTRACT-MIN(Q)

8.			for each v  Adj[u]

9.				do if v  Q and w(u, v) < key[v]

10.					then π[v] ← u

11.						key[v] ← w(u, v)

---

Example

Procedure for finding Minimum Spanning Tree

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

---

C IMPLEMETATION of prim's Algorithm

#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();

}

output

---