Prism Algorithm

ALGORITHM Prim(G)

//Prim’s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graphG = V, E//Output: ET , the set of edges composing a minimum spanning tree of G

VT ← {v0} //the set of tree vertices can be initialized with any vertex

ET ← ∅

for i ← 1 to |V | - 1 dofind a minimum-weight edge e∗ = (v∗, u∗) among all the edges (v, u)such that v is in VT and u is in V - VT

VT ← VT ∪ {u∗}

ET ← ET ∪ {e∗}

return ET  

C program:

#include<stdio.h>

int a,b,u,v,n,i,j,ne=1;

int visited[10]={0},min,mincost=0,cost[10][10];

int main()

{

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++)

{

printf("\nEnter connection bt vertex %c & vertex %c\t",i+64,j+64);

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:(%c->%c) cost:%d",ne++,64+a,64+b,min);

mincost+=min;

visited[b]=1;

}

cost[a][b]=cost[b][a]=999;

}

printf("\n Minimum cost=%d",mincost);

}

Output:

Enter the number of nodes:4

Enter the adjacency matrix:

Enter connection bt vertex A & vertex A 0

Enter connection bt vertex A & vertex B 5

Enter connection bt vertex A & vertex C 0

Enter connection bt vertex A & vertex D 4

Enter connection bt vertex B & vertex A 5

Enter connection bt vertex B & vertex B 0

Enter connection bt vertex B & vertex C 3

Enter connection bt vertex B & vertex D 0

Enter connection bt vertex C & vertex A 0

Enter connection bt vertex C & vertex B 3

Enter connection bt vertex C & vertex C 0

Enter connection bt vertex C & vertex D 4

Enter connection bt vertex D & vertex A 4

Enter connection bt vertex D & vertex B 0

Enter connection bt vertex D & vertex C 4

Enter connection bt vertex D & vertex D 0

 Edge 1:(A->D) cost:4

 Edge 2:(D->C) cost:4

 Edge 3:(C->B) cost:3

 Minimum cost=11