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





Quantitative Aptitude
Reasoning
Programming
Interview