Prim's algorithm is an 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. Prim's algorithm is an example of a greedy algorithm. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim-Jarník algorithm.
The algorithm works by starting from a randomnode and checks the minimum cost for all links for it, then goes to thesecond node and then checks again for the least cost for the two nodes,considering not to visit any visited node.
Program in C++
#include”iostream.h”
#include”conio.h”
#include”stdlib.h”
#include”process.h”
#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999
class point
{
public:
int pre,dist,status;
};
class arc
{
public:
int u,v;
};
int adj[MAX][MAX];
int n;
class graph
{
public:
void creategraph();
void display();
int allperm(class point state[MAX]);
int maketree(class arc tree[MAX],int *weight);
};
void graph::creategraph()
{
int i=0,max_arc,origin,destin,wt;
cout<<"\n Enter the number of vertices:";
cin>>n;
max_arc=n*(n-1)/2;
for(i=1;i<=max_arc;i++)
{
cout<<"\nEnter the edge "<
if((origin==0)&&(destin==0))
break;
cout<<"\nEnter the weight for this arc:";
cin>>wt;
if(origin>n||destin>n||origin<=0||destin<=0)
{
cout<<"\nInvalid arcs";
i--;
}
else
{
adj[origin][destin]=wt;
adj[destin][origin]=wt;
}
}
if(i==0)
{
cout<<"\nSpanning tree not possible";
getch();
exit(0);
}
}
void graph::display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<
cout<<"\n";
}
}
int graph::allperm(class point state[MAX])
{
int i;
for(i=1;i<=n;i++)
{
if(state[i].status==TEMP)
return FALSE;
}
return TRUE;
}
int graph::maketree(class arc tree[MAX],int *weight)
{
class point state[MAX];
int i,min,count,current;
int u1,v1;
*weight=0;
for(i=1;i<=n;i++)
{
state[i].pre=0;
state[i].dist=infinity;
state[i].status=TEMP;
}
state[1].pre=0;
state[1].dist=0;
state[1].status=PERM;
current=1;
count=0;
while(allperm(state)!=TRUE)
{
for(i=1;i<=n;i++)
{
if(adj[current][i]>0 && state[i].status==TEMP)
{
if(adj[current][i] < state[i].dist)
{
state[i].pre=current;
state[i].dist=adj[current][i];
}
}
}
min=infinity;
for(i=1;i<=n;i++)
{
if(state[i].status==TEMP && state[i].dist
min=state[i].dist;
current=i;
}
}
state[current].status=PERM;
u1=state[current].pre;
v1=current;
count++;
tree[count].u=u1;
tree[count].v=v1;
*weight=*weight+adj[u1][v1];
}
return count;
}
void main()
{
graph g;
int i,j;
int path[MAX];
int wttree,count;
class arc tree[MAX];
clrscr();
cout<<"\t\t"<<"PRIMS ALGORITHM";
g.creategraph();
cout<<"\nAdjacency Matrix:\n";
g.display();
count=g.maketree(tree,&wttree);
cout<<"\nWeight of spanningtree arc :"<
for(i=1;i<=count;i++)
{
cout<<"\n"<
getch();
}
For Matrix formation please visit,
http://www.youtube.com/watch?v=sl6W3_Q4HZo
to watch the video.
Regards
