#include<iostream.h>
#include<conio.h>
class newspaper{
public:
int houses;
int dist[10][10],visited[10];
void setpath();
void dfs(int);
void prims(int[10][10],int);
};
void newspaper::setpath(){
int i,j;
cout<<"Enter no of houses";
cin>>houses;
cout<<"Now enter the distance between them..if no route place 999";
for(i=1;i<=houses;i++){
for(j=1;j<=houses;j++){
cout<<"Enter distance between house"<<i<<"to house"<<j;
cin>>dist[i][j];
if(dist[i][j]==0)dist[i][j]=999;
}
}
for(i=1;i<=houses;i++){
visited[i]=0;
}
}
void newspaper::dfs(int k){
int i;
cout<<k;
visited[k]=1;
for(i=1;i<=houses;i++){
if(dist[i][k]!=0||dist[i][k]!=-99){
if(!visited[i])
dfs(i);
}
}
}
void newspaper::prims(int dist[10][10],int n){
int visited[10]={0};
int ne,i,j,a,b,u,v=1;
int minwt,min=0;
visited[1]=1;
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(dist[i][j]<min)
if(visited[i]!=0)
{
min=dist[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
cout<<"\n Edge "<<ne++<<"\t"<<a<<"-"<<b<<"\t"<<min;
minwt+=min;
visited[b]=1;
}
dist[a][b]=dist[b][a]=999;
}
cout<<"\n Minimun cost"<<minwt;
}
void main(){
newspaper np;int k;
clrscr();
np.setpath();
cout<<"Enter the name of house from where to traverse the newspaper";
cin>>k;
cout<<"\n";
cout<<"*********Path as per DFS*********"<<"\n";
np.dfs(k);
cout<<"\n";
cout<<"******************Shortest Path********"<<"\n";
np.prims(np.dist,np.houses);
getch();
}
#include<conio.h>
class newspaper{
public:
int houses;
int dist[10][10],visited[10];
void setpath();
void dfs(int);
void prims(int[10][10],int);
};
void newspaper::setpath(){
int i,j;
cout<<"Enter no of houses";
cin>>houses;
cout<<"Now enter the distance between them..if no route place 999";
for(i=1;i<=houses;i++){
for(j=1;j<=houses;j++){
cout<<"Enter distance between house"<<i<<"to house"<<j;
cin>>dist[i][j];
if(dist[i][j]==0)dist[i][j]=999;
}
}
for(i=1;i<=houses;i++){
visited[i]=0;
}
}
void newspaper::dfs(int k){
int i;
cout<<k;
visited[k]=1;
for(i=1;i<=houses;i++){
if(dist[i][k]!=0||dist[i][k]!=-99){
if(!visited[i])
dfs(i);
}
}
}
void newspaper::prims(int dist[10][10],int n){
int visited[10]={0};
int ne,i,j,a,b,u,v=1;
int minwt,min=0;
visited[1]=1;
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(dist[i][j]<min)
if(visited[i]!=0)
{
min=dist[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
cout<<"\n Edge "<<ne++<<"\t"<<a<<"-"<<b<<"\t"<<min;
minwt+=min;
visited[b]=1;
}
dist[a][b]=dist[b][a]=999;
}
cout<<"\n Minimun cost"<<minwt;
}
void main(){
newspaper np;int k;
clrscr();
np.setpath();
cout<<"Enter the name of house from where to traverse the newspaper";
cin>>k;
cout<<"\n";
cout<<"*********Path as per DFS*********"<<"\n";
np.dfs(k);
cout<<"\n";
cout<<"******************Shortest Path********"<<"\n";
np.prims(np.dist,np.houses);
getch();
}