Graphs Newspaper Boy Problem -CPP

Q:-Implement DFS ,BFS, Prim's and Kruskals algorithms so as to help the newspaper boy deliver the newspapers.

Solution
Language Used:-C++

1. The graph is represented using array data structure. 
2. DFS , BFS , Prim's and Kruskals are written using functions inside the classes 

C++ Code

 

#‎define‬ INF 9999
#define MAX 10
‪#‎include<iostream>
using namespace std;
class Graph{
private:
int lane[MAX];
int hnos,lnos; //number of houses and lanes
int g[MAX][MAX]; //adjacency matrix for graph
int l[MAX]; //array to store the lanes
int tg[MAX][MAX]; //this is temporary graph used for prims and krushkals
public:
Graph(int hnos,int lnos){ //constructor
this->hnos=hnos;
this->lnos=lnos;
lset();
read();
cout<<"The entered graph is as follows"<<endl;
printg();
}
void lset(){ //to read lane nos for each house
int i=0;
while(i<=hnos-1){
cout<<"Enter lane number for house\t"<<i<<endl;
cin>>lane[i];
i++;
}
}
void read(){ //to read the cost adjacency matrix
int i,j; //optimized reading algorithm
cout<<"Enter cost adjacency matrix for the graph"<<endl;
cout<<"Enter -1 for infinity"<<endl;
for(i=0;i<=hnos-1;i++){
for(j=i;j<=hnos-1;j++){
if(i==j){g[i][j]=0;continue;}
cout<<"Enter cost for edge\t"<<i<<","<<j<<endl;
cin >>g[i][j];
if(g[i][j]==-1)
g[i][j]=INF;
g[j][i]=g[i][j];
}
}
}
void printg(){ //to print the graph
int i,j;
for(i=0;i<=hnos-1;i++){
for(j=0;j<=hnos-1;j++){
cout<<g[i][j]<<"\t";
}
cout<<endl;
}
}
void prims(){ //prims algorithm for shortest path
int visited[MAX];
int tg[MAX][MAX];
for(int i=0;i<=hnos-1;i++){ //initialize visited array
visited[i]=0;
}
for(int i=0;i<hnos;i++) //initialize the house array
for(int j=0;j<hnos;j++)
tg[i][j]=0;
int distance[MAX]; //array to store the distances
int from[MAX]; //to store the vertex from which the distance is minimum
int edgeno=0;
int cost=0;
int i;
int vertex,source; //vertex is the selected vertex ,source is from the "from" array
int min; //temporary variable
distance[0]=0; //begin from vertex zero
visited[0]=1;
for(i=1;i<=hnos-1;i++)
{
distance[i]=g[0][i]; //set the distances from zero
from[i]=0;
}
while(edgeno<hnos-1){
min=INF;
for(i=0;i<=hnos-1;i++){
if(distance[i]<min&&visited[i]==0){
min=distance[i];
vertex=i; //this is the vertex to be visited
}
} //first for loop ends here
if(min==INF){
cout<<"No spanning tree exists"<<endl;
return;
}
visited[vertex]=1;
source=from[vertex];
tg[source][vertex]=tg[vertex][source]=distance[vertex];
cost=cost+distance[vertex];
for(i=0;i<=hnos-1;i++){ //updating of distances from new vertex
if(visited[i]==0&&g[vertex][i]<distance[i]){
distance[i]=g[vertex][i];
from[i]=vertex;
}
}
edgeno++;
}
cout<<"The spanning tree is as follows"<<endl;
for(i=0;i<=hnos-1;i++){
for(int j=0;j<=hnos-1;j++){ //Error was hnos++
cout<<tg[i][j]<<"\t";
}
cout<<endl;
}
cout<<"The cost of the spanning tree is "<<cost<<endl;
}
void kruskals(){
int tg[MAX][MAX],result[MAX][MAX];//tg=coypgraph,result=answer
int father[MAX]; //array to prevent cycles
int i,j,edge=0,cost=0,min,t1,t2,root1,root2,temp1,temp2;
for(i=0;i<=hnos-1;i++){ //initialize stuff
father[i]=-1;
for(j=0;j<=hnos-1;j++)
tg[i][j]=g[i][j];
}
for(i=0;i<=hnos-1;i++)
for(j=0;j<=hnos-1;j++){
result[i][j]=0;
}
while(edge!=hnos-1&&min!=INF){ //find edge with minimum weight
min=INF;
for(i=0;i<=hnos-1;i++){
for(j=0;j<=hnos-1;j++){
if(min>tg[i][j]&&tg[i][j]!=0){
min=tg[i][j];
t1=i;
t2=j;
}
}
}
temp1=t1+0;
temp2=t2+0;
while(t1>-1){ //cycle checking begins
root1=t1;
t1=father[t1];
}
while(t2>-1){
root2=t2;
t2=father[t2];//Last error corrected instead of t2 only 2 was written
}
if(root1!=root2){//if not a cycle
result[temp1][temp2]=g[temp1][temp2];
result[temp2][temp1]=g[temp1][temp2];
cost=cost+g[temp1][temp2];
father[root2]=root1;
edge++;
}
tg[temp1][temp2]=0; //delete the used edge
tg[temp2][temp1]=0;
}
if(edge!=hnos-1){
cout<<"No spanning tree exists"<<endl;
return;
}
cout<<"The spanning tree is as follows"<<endl;
for(i=0;i<=hnos-1;i++){
cout<<endl;
for(j=0;j<=hnos-1;j++){
cout<<result[i][j]<<"\t";
}
}
cout<<"\nthe cost of the spanning tree is "<<cost<<endl;
}
void dfs(int v){ //recursive function for dfs
static int visited[MAX]; //this array is declared only
static int j=1; //flag is initialized once
if(j==1){ //only executed during first call
for(int i=0;i<=hnos-1;i++){
visited[i]=0;
}
}
j=0;
visited[v]=1;
cout<<"Visited "<< v <<endl;
for(int j=0;j<=hnos-1;j++){
if(visited[j]==0 && g[v][j]!=INF && g[v][j]!=0){
cout<< "used edge\t "<<v<<","<<j<<endl;
dfs(j);
}
}
}
void bfs(int v){
int visited[MAX];
int q[20]; //queue array
int front=0,rear=0; //counter for queue
int i;
for(i=0;i<=hnos-1;i++)
visited[i]=0;
visited[v]=1;
q[rear++]=v;
//cout<<"inserting " <<v<<"front"<<front<<"rear"<<rear<<endl;
cout<<v<<"\t";
while(front!=rear){ //queue is not empty
v=q[front++];
//cout<<"poping " <<v<<"front"<<front<<"rear"<<rear<<endl;
for(i=0;i<=hnos-1;i++){
if(visited[i]==0 &&g[v][i]!=INF){
cout<<i<<"\t";
visited[i]=1;
q[rear++]=i;
//cout<<"inserting " <<i<<"front"<<front<<"rear"<<rear<<endl;
}
}
}
cout<<endl;
}
};
int main() {
int hnos,lnos,choice=-1,vertex=-1;
cout << "Newspaper Delivery Problem" << endl; // prints Newspaper Delivery Problem
cout <<"Enter the number of houses"<< endl;\
cin >> hnos;
cout << "Enter the number of lanes" <<endl;
cin >>lnos;
Graph a(hnos,lnos);
while(choice!=5){
cout<<"Enter ur choice"<<endl;
cout<<"1.dfs 2.krushkal 3.prims 4.bfs 5.exit"<<endl;
cin >>choice;
switch(choice){
case 1:
cout<<"enter the vertex for dfs"<<endl;
cin>>vertex;
a.dfs(vertex);
break;
case 2:
a.kruskals();
break;
case 3:
a.prims();
break;
case 4:
cout<<"enter the vertex for bfs"<<endl;
cin>>vertex;
a.bfs(vertex);
break;
case 5:
cout<<"terminating program"<<endl;
break;
default:
cout<<"invalid choice entered\n Enter again"<<endl;
break;
}
}
return 0;

 

You may also want to check out:-

• Topological Sort