# Prim’s Algorithm for Minimum Spanning tree

/************************************************************

-> This Program is to implement Prims algorithm.

-> This program is to find minimum spanning tree
for undirected weighted graphs

-> Data Structers used:

-> This program works in microsoft vc++ 6.0 environment.

**************************************************************/

#include<iostream.h>

class prims
{
private:
int n; //no of nodes
int graph_edge; //edges in the graph
int g; //no of edges in the graph
int tree_edge; //edges in the tree
int t; //no of edges in the tree
int s; //source node

//Partition the graph in to two sets
int T1,t1; // Set 1
int T2,t2; // Set 2

public:
void input();
int findset(int);
void algorithm();
void output();
};
void prims::input()
{
cout<<“*************************************************\n”
<<“This program implements the prims algorithm\n”
<<“*************************************************\n”;
cout<<“Enter the no. of nodes in the undirected weighted graph ::”;
cin>>n;

g=0;

cout<<“Enter the weights for the following edges ::\n”;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<” < “<<i<<” , “<<j<<” > ::”;
int w;
cin>>w;
if(w!=0)
{
g++;

graph_edge[g]=i;
graph_edge[g]=j;
graph_edge[g]=w;
}
}
}

// print the graph edges

cout<<“\n\nThe edges in the given graph are::\n”;
for(i=1;i<=g;i++)
cout<<” < “<<graph_edge[i]
<<” , “<<graph_edge[i]
<<” > ::”<<graph_edge[i]<<endl;
}

int prims::findset(int x)
{
for(int i=1;i<=t1;i++)
if(x==T1[i])
return 1;

for(i=1;i<=t2;i++)
if(x==T2[i])
return 2;
return -1;
}

void prims::algorithm()
{
t=0;

t1=1;
T1=1; //The source node

t2=n-1;
int i;
for(i=1;i<=n-1;i++)
T2[i]=i+1; //The reamining nodes

cout<<“\n*****The algorithm starts*****\n\n”;

while(g!=0 && t!=n-1)
{
// Find the least cost edge
int min=9999;
int p;
int u,v,w;
for(i=1;i<=g;i++)
{
bool flag1=false,flag2=false;

//if u and v are in different sets
if(findset(graph_edge[i])!=findset(graph_edge[i]))
{
if(min>graph_edge[i])
{
min=graph_edge[i];
u=graph_edge[i];
v=graph_edge[i];
w=graph_edge[i];

p=i;
}
}
}

//break if there is no such edge

cout<<“The edge included in the tree is ::”;
cout<<” < “<<u<<” , “<<v<<” > “<<endl;

//delete the edge from graph edges

for(int l=p;l<g;l++)
{
graph_edge[l]=graph_edge[l+1];
graph_edge[l]=graph_edge[l+1];
graph_edge[l]=graph_edge[l+1];
}
g–;

//add the edge to the tree

t++;
tree_edge[t]=u;
tree_edge[t]=v;
tree_edge[t]=w;

//Alter the set partitions
t1++;

int m;
if(findset(v)==2)
{
T1[t1]=v;
m=v;
}
else if(findset(u)==2)
{
T1[t1]=u;
m=u;
}

int x;
for(x=1;T2[x]!=m;x++);

for(;x<t2;x++)
T2[x]=T2[x+1];
t2–;

// Print the sets

int k;
cout<<“NOW\nT1 :: “;
for(k=1;k<=t1;k++)
cout<<T1[k]<<‘ ‘;
cout<<endl;

cout<<“T2 :: “;
for(k=1;k<=t2;k++)
cout<<T2[k]<<‘ ‘;
cout<<endl;

cout<<“The graph edges are ::\n”;
for(i=1;i<=g;i++)
cout<<” < “<<graph_edge[i]
<<” , “<<graph_edge[i]
<<” > ::”<<graph_edge[i]<<endl;

cout<<endl<<endl;

}
}

void prims::output()
{
cout<<“\nThe selected edges are ::\n”;
for(int i=1;i<=t;i++)
cout<<” < “<<tree_edge[i]
<<” , “<<tree_edge[i]
<<” > ::”<<tree_edge[i]<<endl;
}
int main()
{
prims obj;
obj.input();
obj.algorithm();
obj.output();
return 0;
}

## 18 thoughts on “Prim’s Algorithm for Minimum Spanning tree”

1. papyrus says:

Thank you for this useful notes & programs.

2. Tamal says:

This coding can’t run by any compiler it is very tough to correct this program by any compiler. So do it in a easy way that anybody can easily understand your code and implement in a simplest way. Anyway Thank you for providing this code.
Tamal
CSE,JU
Dhaka

3. Manu says:

// Modified code im sure it ll work with gcc
// i compiled it using Bloodshed
// This is really simple logic
// accidentially the author & me implimented almost same logic
// But this one is only a modified version of the original file
// manuvs@msn.com

#include
#include
class prims
{
private:
int n; //no of nodes
int graph_edge; //edges in the graph
int g; //no of edges in the graph
int tree_edge; //edges in the tree
int t; //no of edges in the tree
int s; //source node
int i;

//Partition the graph in to two sets
int T1,t1; // Set 1
int T2,t2; // Set 2

public:
void input();
int findset(int);
void algorithm();
void output();
};
void prims::input()
{
cout<<“*************************************************\n”
<<“This program implements the prims algorithm\n”
<<“*************************************************\n”;
cout<>n;

g=0;

cout<<“Enter the weights for the following edges ::\n”;
for(i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<” < “<<i<<” , “<<j< ::”;
int w;
cin>>w;
if(w!=0)
{
g++;

graph_edge[g]=i;
graph_edge[g]=j;
graph_edge[g]=w;
}
}
}

// print the graph edges

cout<<“\n\nThe edges in the given graph are::\n”;
for(i=1;i<=g;i++)
cout<<” < “<<graph_edge[i]
<<” , “<<graph_edge[i]
< ::”<<graph_edge[i]<<endl;
}

int prims::findset(int x)
{
for(i=1;i<=t1;i++)
if(x==T1[i])
return 1;

for(i=1;i<=t2;i++)
if(x==T2[i])
return 2;
return -1;
}

void prims::algorithm()
{
t=0;

t1=1;
T1=1; //The source node

t2=n-1;
int i;
for(i=1;i<=n-1;i++)
T2[i]=i+1; //The reamining nodes

cout<<“\n*****The algorithm starts*****\n\n”;

while(g!=0 && t!=n-1)
{
// Find the least cost edge
int min=9999;
int p;
int u,v,w;
for(i=1;igraph_edge[i])
{
min=graph_edge[i];
u=graph_edge[i];
v=graph_edge[i];
w=graph_edge[i];

p=i;
}
}
}

//break if there is no such edge

cout<<“The edge included in the tree is ::”;
cout<<” < “<<u<<” , “<<v< “<<endl;

//delete the edge from graph edges

for(int l=p;l<g;l++)
{
graph_edge[l]=graph_edge[l+1];
graph_edge[l]=graph_edge[l+1];
graph_edge[l]=graph_edge[l+1];
}
g–;

//add the edge to the tree

t++;
tree_edge[t]=u;
tree_edge[t]=v;
tree_edge[t]=w;

//Alter the set partitions
t1++;

int m;
if(findset(v)==2)
{
T1[t1]=v;
m=v;
}
else if(findset(u)==2)
{
T1[t1]=u;
m=u;
}

int x;
for(x=1;T2[x]!=m;x++);

for(;x<t2;x++)
T2[x]=T2[x+1];
t2–;

// Print the sets

int k;
cout<<“NOW\nT1 :: “;
for(k=1;k<=t1;k++)
cout<<T1[k]<<” “;
cout<<endl;

cout<<“T2 :: “;
for(k=1;k<=t2;k++)
cout<<T2[k]<<” “;
cout<<endl;

cout<<“The graph edges are ::\n”;
for(i=1;i<=g;i++)
cout<<” < “<<graph_edge[i]
<<” , “<<graph_edge[i]
< ::”<<graph_edge[i]<<endl;

cout<<endl<<endl;

}
}

void prims::output()
{
cout<<“\nThe selected edges are ::\n”;
for(int i=1;i<=t;i++)
cout<<” < “<<tree_edge[i]
<<” , “<<tree_edge[i]
< ::”<<tree_edge[i]<<endl;
}
int main()
{
prims obj;
obj.input();
obj.algorithm();
obj.output();
system(“PAUSE”);
return 0;
}

4. s4v1our says:

can you make that program in java?

5. RDX!! says:

can u create it in java?

6. leon says:

thank you 4 this useful code of prim
^0^

7. gayathri says:

anybody having Prim’s algorithm using c Coding.

1. dilip says:

ya give ur mobile number

8. gayathri says:

9. DIANA says:

it is very useful for beginners…………..thanks

10. amee says:

waahh kereenn..:)

11. pradeep says:

can some1 give tha c code of this program using heap?????

12. adison says:

not so good

13. nsr says:

itzz nice

14. yasir says:

could you please tell me how to represent this result in graphic form. using graphics.h????

15. www.set222.com says:

What’s up, constantly i used to check webpage posts here in the early hours in the break of day, as i like to gain knowledge of more and more.