Home / Algorithms / C program to find Minimum Spanning tree PRIM’s Algorithm

C program to find Minimum Spanning tree PRIM’s Algorithm

C program to find 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.

General apporach for writing a C Code to Find Minimum Spanning tree using PRIM’s Algorithm :

  • create a tree containing a single vertex, chosen arbitrarily from the graph

  • create a set containing all the edges in the graph

  • loop until every edge in the set connects two vertices in the tree

    • remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree

    • add that edge to the tree

Let’s see how to write a of PRIM’s Algorithm to find Minimum Spanning tree.

C program to find Minimum Spanning tree using PRIM’s Algorithm :

 

#include<stdio.h>
#define INF 1000
int vertex[10];
int wght[10][10];
int new_wght[10][10];
int closed[10];
int n;
int inclose(int i,int n1)
{
/*chk for the ith vertex presence in closed*/
int j;
for(j=0;j<=n1;j++)
if(closed[j]==i)
return 1;
return 0;
}
void buildtree()
{
int i=0,j,count=0;
int min,k,v1=0,v2=0;
closed[0]=0;
while(count<n-1)
{
min=INF;
for(i=0;i<=count;i++)
for(j=0;j<n;j++)
if(wght[closed[i]][j]<min && !inclose(j,count))
{
min=wght[closed[i]][j];
v1=closed[i];
v2=j;
}
new_wght[v1][v2]=new_wght[v2][v1]=min;
count++;
closed[count]=v2;
printf("\nScan : %d %d---------%d wght = %d \n",count,v1+1,v2+1,min);
getch();
}
}
void main()
{
int i,j,ed,sum=0;
clrscr();
printf("\n\n\tPRIM'S ALGORITHM TO FIND SPANNING TREE\n\n");
printf("\n\tEnter the No. of Nodes : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
vertex[i]=i+1;
for(j=0;j<n;j++)
{
wght[i][j]=INF;
new_wght[i][j]=INF;
}
}
printf("\n\nGetting Weight.\n");
printf("\n\tEnter 0 if path doesn't exist between {v1,v2} else enter the wght\n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
printf("\n\t%d -------- %d : ",vertex[i],vertex[j]);
scanf("%d",&ed);
if(ed>=1)
wght[i][j]=wght[j][i]=ed;
}
getch();
clrscr();
printf("\n\n\t\tNODES CURRENTLY ADDED TO SPANNING TREE\n\n");
buildtree();
printf("\n\tNEW GRAPH WEIGHT MATRIX\n\n");
printf("\n\tweight matrix\n\n\t");
for(i=0;i<n;i++,printf("\n\t"))
for(j=0;j<n;j++,printf("\t"))
printf("%d",new_wght[i][j]);
printf("\n\n\t\tMINIMUM SPANNING TREE\n\n");
printf("\n\t\tLIST OF EDGES\n\n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(new_wght[i][j]!=INF)
{
printf("\n\t\t%d ------ %d = %d ",vertex[i],vertex[j],new_wght[i][j]);
sum+=new_wght[i][j];
}
printf("\n\n\t Total Weight : %d ",sum);
getch();
}

We hope you all have enjoyed the C program of PRIM’s Algorithm to find minimum spanning tree. If you have any doubts or queries ask us in form of comments.

About Mr Coder

Well, I am software programmer and love to code. My hobbies is to do Hacking, Coding, Blogging, Web Designing and playing online games. Feel free to contact me at shiviskingg@gmail.com or lokesh@hackingloops.com

Check Also

C Program to Implement Stack

This C Program implements stack. Stack is an area of memory that holds all local …

2 comments

  1. “Email This Post” allows your blog readers to share
    your posts with their friends. 4Under the Basic
    Tab, you will see Blog Tools, and the links to Import blog, Export blog,
    or Delete blog.

  2. Doing so will entail interest in the information you’re discussing
    on the blog and possibly earn you repeat visitors. Check out for many helpful tips including ways to get inspiration for blog posts.

Leave a Reply

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