/****************************************************************
NAME :-
Jabir Daud Pathan
PROGRAM
:- Represent graph using adjacency list or
matrix
and generate minimum spanning tree using
Prism’s
algorithm
*****************************************************************/
/*------------<< Header File
>>------------*/
#include<iostream.h>
#include<conio.h>
#define
size 40
#define
infinity 32767
/*-------<< Declaration of class mst >>--------*/
class
mst
{
int m[size][size],nodes;
public :
mst();
void accept();
void prims();
};
/*-------<< Defination of Constructor (outside the class)
>>--------*/
mst::mst()
{
int i,j;
for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
m[i][j]=0;
}
}
}
/*-------<< Function defination for creating graph
>>-------*/
void
mst::accept()
{
int n,v1,v2,i,wt;
cout<<"\nEnter the total no of
vertices :";
cin>>nodes;
cout<<"\nHow many edges you want
to enter :";
cin>>n;
cout<<"\nEnter vertices :\n";
for(i=0;i<n;i++)
{
cout<<"\nEnter the v1 and v2 :
";
cin>>v1>>v2;
cout<<"\nEnter the weight of
corresponding edge :";
cin>>wt;
m[v1][v2]=m[v2][v1]=wt;
}
}
/*--<< Function defination for to find MST using
prims algorithm >>---*/
void
mst::prims()
{
int v1,v2,mwt,total=0;
int select[size];
int i,j,k;
for(i=0;i<nodes;i++)
select[i]=0;
cout<<"\n\nMinimum Spanning Tree
using Prim's Algorithm is :\n";
select[0]=1;
for(k=1;k<nodes;k++)
{
mwt=infinity;
for(i=0;i<nodes;i++)
{
for(j=0;j<nodes;j++)
{
if(m[i][j]&&((select[i]&&!select[j])||(!select[i]&&select[j])))
{
if(m[i][j]<mwt)
{
mwt=m[i][j];
v1=i;
v2=j;
}
}
}
}
cout<<"\n\tEdge
("<<v1<<" "<<v2<<") and its weight
= "<<mwt<<endl;
select[v1]=select[v2]=1;
total=total+mwt;
}
cout<<"\n\nMinimum cost of
spanning tree is : "<<total;
}
/*-------------<< Main Function Starts >>------------*/
void
main()
{
mst j;
//creating object of class mst
clrscr();
cout<<"\t\t-----<< PRIM'S
ALGORITHM >>-----\n";
j.accept();
j.prims();
getch();
}
/*-------------<< End Of Main Function >>---------------*/
/*-----------------<< OUTPUT
SCREEN >>-------------------*/
-----<< PRIM'S ALGORITHM
>>-----
Enter
the total no of vertices :7
How
many edges you want to enter :11
Enter
vertices :
Enter
the v1 and v2 : 0 1
Enter
the weight of corresponding edge :5
Enter
the v1 and v2 : 0 2
Enter
the weight of corresponding edge :2
Enter
the v1 and v2 : 1 2
Enter
the weight of corresponding edge :2
Enter
the v1 and v2 : 1 3
Enter
the weight of corresponding edge :6
Enter
the v1 and v2 : 2 3
Enter
the weight of corresponding edge :7
Enter
the v1 and v2 : 1 4
Enter
the weight of corresponding edge :25
Enter
the v1 and v2 : 2 5
Enter
the weight of corresponding edge :10
Enter
the v1 and v2 : 3 6
Enter
the weight of corresponding edge :12
Enter
the v1 and v2 : 4 5
Enter
the weight of corresponding edge :14
Enter
the v1 and v2 : 4 6
Enter
the weight of corresponding edge :11
Enter
the v1 and v2 : 5 6
Enter
the weight of corresponding edge :15
Minimum
Spanning Tree using Prim's Algorithm is :
Edge (0 2) and its weight = 2
Edge (1 2) and its weight = 2
Edge (1 3) and its weight = 6
Edge (2 5) and its weight = 10
Edge (3 6) and its weight = 12
Edge (4 6) and its weight = 11
Minimum
cost of spanning tree is : 43
/******************************************************************/
No comments:
Post a Comment