3.prims

File: /home/saiesh/ADS/Assignment No 3/ads3.cpp
Page 1 of 3
#include<iostream>
#include<stdlib.h>
using namespace std;
class prims
{
private:
int nodes;
int w[10][10];
int visited[10];
public:
void accept();
void prim();
};
void prims::accept()
{
int i,j;
cout<<"\nHow many number of nodes do you want to accept? ";
cin>>nodes;
for(i=0;i<nodes;i++)
{
for(j=i+1;j<nodes;j++)
{
cout<<"\nEnter the value of ["<<i<<"]["<<j<<"]:\t";
cin>>w[i][j];
w[j][i]=w[i][j];
}
}
for(i=0;i<nodes;i++)
{
for(j=0;j<nodes;j++)
{
if(i==j)
w[i][j]=0;
}
}
for(i=0;i<nodes;i++)
{
cout<<"\n";
for(j=0;j<nodes;j++)
cout<<"\t"<<w[i][j];
}
}
void prims::prim()
{
int i,j,totalcost=0,min=9999,k,l,m,st;
cout<<"\nEnter the starting vertex: ";
cin>>st;
for(i=0;i<nodes;i++)
visited[i]=0;
visited[st]=1;
for(j=0;j<nodes;j++)
{
if(w[st][j]!=0&&w[st][j]<min)
{
min=w[st][j];
k=st;
l=j;
}
}
cout<<"\nEdge ("<<k<<","<<l<<") is having minimum cost: "<<min;
visited[k]=visited[l]=1;
totalcost=min;
for(m=0;m<nodes-2;m++)
{File: /home/saiesh/ADS/Assignment No 3/ads3.cpp
Page 2 of 3
min=9999;
for(i=0;i<nodes;i++)
{
if(visited[i]==1)
{
for(j=0;j<nodes;j++)
{
if(visited[j]!=1)
{
if(w[i][j]!=0&&w[i][j]<min)
{
min=w[i][j];
k=i;
l=j;
}
}
}
}
}
cout<<"\nEdge ("<<k<<","<<l<<") is having minimum cost: "<<min;
visited[k]=visited[l]=1;
totalcost=totalcost+min;
}
cout<<"\nTotal cost is: "<<totalcost;
}
int main()
{
prims obj;
int ch;
char ans;
do
{
cout<<"\n\tMENU";
cout<<"\n1.Accept the graph";
cout<<"\n2.Minimum spanning tree";
cout<<"\n3.Exit";
cout<<"\nEnter your choice:\t";
cin>>ch;
switch(ch)
{
case 1: obj.accept();
break;
case 2: obj.prim();
break;
case 3: exit(0);
}
cout<<"\nDo you want to continue? ";
cin>>ans;
} while(ans=='y'||ans=='Y');
return 0;
}
/*
OUTPUT
saiesh@saiesh :~$ g++ ads3.cpp
saiesh@saiesh :~$ ./a.out
MENU
1.Accept the graph
2.Minimum spanning tree
3.Exit
Enter your choice:
1
How many number of nodes do you want to accept? 4
Enter the value of [0][1]:
1File: /home/saiesh/ADS/Assignment No 3/ads3.cpp
Enter
Enter
Enter
Enter
Enter
the
the
the
the
the
value
value
value
value
value
of
of
of
of
of
[0][2]:
[0][3]:
[1][2]:
[1][3]:
[2][3]: 0
7
5
0
2
0
1
0
1
0
5
0
5
0
7
0
2
Do you want to continue? y 7
0
2
0
MENU
1.Accept the graph
2.Minimum spanning tree
3.Exit
Enter your choice:
2
Enter the starting vertex: 0
Edge (0,1) is having minimum cost: 1
Edge (1,2) is having minimum cost: 5
Edge (2,3) is having minimum cost: 2
Total cost is: 8
Do you want to continue? y
MENU
1.Accept the graph
2.Minimum spanning tree
3.Exit
Enter your choice:
2
Enter the starting vertex: 1
Edge (1,0) is having minimum cost: 1
Edge (1,2) is having minimum cost: 5
Edge (2,3) is having minimum cost: 2
Total cost is: 8
Do you want to continue? y
MENU
1.Accept the graph
2.Minimum spanning tree
3.Exit
Enter your choice:
2
Enter the starting vertex: 2
Edge (2,3) is having minimum cost: 2
Edge (2,1) is having minimum cost: 5
Edge (1,0) is having minimum cost: 1
Total cost is: 8
Do you want to continue? y
MENU
1.Accept the graph
2.Minimum spanning tree
3.Exit
Enter your choice:
2
Enter the starting vertex: 3
Edge (3,2) is having minimum cost: 2
Edge (2,1) is having minimum cost: 5
Edge (1,0) is having minimum cost: 1
Total cost is: 8
Do you want to continue? y
MENU
1.Accept the graph
2.Minimum spanning tree
3.Exit
Enter your choice:
3
saiesh@saiesh :~$ */
Page 3 of 3