DSPS: paper boy (dfs traversal_graph)
//============================================================================
// Name : newpaper_boy.cpp
// Author : Parashar
// Version :
// Copyright : Do not try this at home
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
using namespace std;
#define True 1
#define False 0
#define size 10
class graph
{
public:
int n,e;
int g[size][size],q[size];
int front,rear;
int visit[size];
int dist;
public:
graph();
void create();
void dfs(int);
void visited();
};
graph::graph()
{
front=rear=-1;
for(int v1=0;v1<size;v1++)
{
for(int v2=0;v2<size;v2++)
{
g[v1][v2]=g[v2][v1]=False;
}
}
}
void graph::visited()
{
for(int i=0;i<size;i++)
visit[i]=False;
dist=0;
}
void graph::create()
{
int v1,v2,dist;
cout<<"\nEnter the number of lanes:";
cin>>n;
cout<<"\nEnter Total number of paths leading to lanes:";
cin>>e;
for(int i=0;i<e;i++)
{
cout<<"\nEnter the lane a and b:";
cin>>v1>>v2;
cout<<"\nEnter the distance between the lane's entered: ";
cin>>dist;
g[v1][v2]=g[v2][v1]=dist;
}
cout<<"\n The Entered Graph is "<<endl;
for(int v1=0;v1<n;v1++)
{
cout<<"| ";
for(int v2=0;v2<n;v2++)
{
cout<<g[v1][v2]<<" ";
}
cout<<"|";
cout<<endl;
}
}
void graph::dfs(int v1)
{
int v2;
visit[v1]=True;
cout<<v1<<" ";
for(v2=0;v2<n;v2++)
{
if(g[v1][v2]!=false && visit[v2]==false)
{
dist=dist+g[v1][v2];
dfs(v2);
}
}
}
int main()
{
graph obj;
int lane=0;
int path,small=999;
obj.create();
cout<<endl<<"The newspaper boy has following paths to distribute newspaper : "<<endl;
while(lane<obj.n)
{
obj.visited();
cout<<"The way from lane "<<lane<<" is ";
obj.dfs(lane);
cout<<" And the total path length "<<obj.dist;
cout<<endl;
if(obj.dist<small)
{
small=obj.dist;
path=lane;
}
lane++;
}
cout<<endl<<"The Newspaper boy should start distributing newspaper from lane "<<path;
cout<<" which has least distance of "<<small;
return 0;
}
// Name : newpaper_boy.cpp
// Author : Parashar
// Version :
// Copyright : Do not try this at home
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
using namespace std;
#define True 1
#define False 0
#define size 10
class graph
{
public:
int n,e;
int g[size][size],q[size];
int front,rear;
int visit[size];
int dist;
public:
graph();
void create();
void dfs(int);
void visited();
};
graph::graph()
{
front=rear=-1;
for(int v1=0;v1<size;v1++)
{
for(int v2=0;v2<size;v2++)
{
g[v1][v2]=g[v2][v1]=False;
}
}
}
void graph::visited()
{
for(int i=0;i<size;i++)
visit[i]=False;
dist=0;
}
void graph::create()
{
int v1,v2,dist;
cout<<"\nEnter the number of lanes:";
cin>>n;
cout<<"\nEnter Total number of paths leading to lanes:";
cin>>e;
for(int i=0;i<e;i++)
{
cout<<"\nEnter the lane a and b:";
cin>>v1>>v2;
cout<<"\nEnter the distance between the lane's entered: ";
cin>>dist;
g[v1][v2]=g[v2][v1]=dist;
}
cout<<"\n The Entered Graph is "<<endl;
for(int v1=0;v1<n;v1++)
{
cout<<"| ";
for(int v2=0;v2<n;v2++)
{
cout<<g[v1][v2]<<" ";
}
cout<<"|";
cout<<endl;
}
}
void graph::dfs(int v1)
{
int v2;
visit[v1]=True;
cout<<v1<<" ";
for(v2=0;v2<n;v2++)
{
if(g[v1][v2]!=false && visit[v2]==false)
{
dist=dist+g[v1][v2];
dfs(v2);
}
}
}
int main()
{
graph obj;
int lane=0;
int path,small=999;
obj.create();
cout<<endl<<"The newspaper boy has following paths to distribute newspaper : "<<endl;
while(lane<obj.n)
{
obj.visited();
cout<<"The way from lane "<<lane<<" is ";
obj.dfs(lane);
cout<<" And the total path length "<<obj.dist;
cout<<endl;
if(obj.dist<small)
{
small=obj.dist;
path=lane;
}
lane++;
}
cout<<endl<<"The Newspaper boy should start distributing newspaper from lane "<<path;
cout<<" which has least distance of "<<small;
return 0;
}
Comments
Post a Comment