Home / C / C program for Prim’s Algorithm

C program for Prim’s Algorithm

#include<conio.h>
#include<stdio.h>
#define IN 99
int dist[10],path[10];
int extract_min(int Q[], int n)
{
int i,temp[10],t=0,pos;
for(i=0;i<n;i++)
{
if(Q[i]!=-1)
temp[i]=1;
else
temp[i]=0;
}

for(i=0;i<n;i++)
{
if(t==0 && temp[i]==1)
{pos =i;
t=1;
continue;
}
if(temp[i]==1)
if(dist[i]<dist[pos])
pos=i;
}
return pos;
}
int contain(int Q[],int v,int n)
{
int i;
for(i=0;i<n;i++)
if(Q[i]==v+1)
return 1;
return 0;
}
int isempty(int Q[], int n)
{
int i;
for(i=0;i<n;i++)
{
if(Q[i]!=-1)
return 0;
}
return 1;
}
void initialize(int n,int s)
{
int i;
for(i=0;i<n;i++)
{
dist[i]=IN;
path[i]=-1;
}
dist[s]=0;
}

//Module which implement prim algorithm

void prim(int edge[10][10],int n,int s)
{
int Q[10],i,u,v,alt;

//Initialization step

initialize(n,s);
for(i=0;i<n;i++)
Q[i]=i+1;
while(isempty(Q,n)==0)
{
u=extract_min(Q,n);
Q[u]=-1;
if(dist[u]==IN)
break;
for(i=0;i<n;i++)
{
if(edge[u][i]!=0 && edge[u][i]!=IN)
{
v=i;
if(edge[u][i]<dist[v] &&="" contain(q,v,n)="=1)<br">{
dist[v]=edge[u][i];
path[v]=u+1;
}
}
}
}
}

void main()
{
int n,edge[10][10],i,j,s,t,wt=0;
clrscr();
printf("Enter total number of vertices");
scanf("%d",&n);

//printf("\nEnter Edge matrix in row major order");

printf(":  Enter 99 for Infinity\n");
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
printf("Enter the edge between %d and %d: ",i+1,j+1);
scanf("%d",&edge[i][j]);
edge[j][i]=edge[i][j];
}
edge[i][i]=0;
}
printf("\n");
printf("Enter the source for MST: ");
scanf("%d",&s);
prim(edge,n,s-1);
printf("\nPATH OF MINIMUM SPANNING TREE is\n");
for(i=0;i<n;i++)
{
if(s-1==i)
continue;
if(dist[i]==IN)
{
printf("PATH from %d to %d not exist\n",i+1,s);
}
else
{
printf("PATH from %d to %d is %d:",i+1,s,i+1);
t=i;
for(j=1;j<n;j++)
{
printf("<--%d",path[t]);
if(path[t]==s)
break;
t=path[t]-1;
}
printf("\n");
}
wt+=dist[i];
 }
printf("\nMinimum Weight of a Graph is %d",wt);
getch();
}

OUTPUT

Tags: Prim’s algorithm implementation, C program for Prim’s algorithm, Minimum Spanning Tree , algorithm to find Minimum Spanning Tree
Also See:   c program to swap two numbers without using a third variable

Check Also

How to Solve Linear Equation in One Variable In C Programming?

C Program to Solve any Linear Equation in One Variable Find complete C program to ...

Leave a Reply

Your email address will not be published. Required fields are marked *