Monday, 25 August 2014

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;
}

No comments:

Post a Comment