1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

DFS and BFS in Graph

Discussion in 'C' started by vkiransrinivas, Nov 12, 2007.

  1. vkiransrinivas

    vkiransrinivas New Member

    Joined:
    Jun 13, 2007
    Messages:
    9
    Likes Received:
    0
    Trophy Points:
    0
    I have problem on this program please solve this if is possible
    on Depth First Search and Breadth First Search
    Some Errors are there please clear if it is possible

    Program
    Code:
    #include<iostream.h>
    #include<conio.h>
    #define true 1
    #define false 0
    
    class node
    {
    int data;    //each node contain adjancent vertex
    node *link;
    friend class graph;
    };
    
    
    class graph     //we can use data link in graph class
    {
    private:
    		int n;    //vertex
    		int e;    //edge
    		sll<int> *a; //array of sll objects vertex num are integer
    public:
    		graph();  //initialise  n,e
    		~graph(); //delete all the linked list in the array
    		void create(); // create all the linked list
    		void display(); // display all the linked list
    		int degree(int i); //return the depth of ith vertex
    		void bft();
    		void dft();
    		void traverse(int j,int * visited);
    		void nov(); //return no of vertex
    		void noe(); //return no of edges
    };
    
    graph::graph()
    {
    cout<<"Enter the no of vertex\n";
    cin>>n;
    cout<<"Enter the no of edges of graph\n";
    cin>>e;
    a=new sll<int>[n];
    }
    
    void graph::create()
    {
    for(int i=0;i<=n-1;i++)
    {
    cout<<"Enter adjancent vertices of "<<i<<"in ascending order terminated -1"<<"\n";
    a[i].create();
    }
    }
    
    int graph::degree(int i)
    {
    return(a[i].length())
    }
    
    int graph::nov()
    {
    return(n);
    }
    int graph::noe()
    {
    return(e);
    }
    
    graph::~graph()
    {
    for(int i=0;i<n-1;i++)
    a[i].erase();
    delete[] a;
    }
    
    void graph::display()
    {
    for(int i=0;i<n-1;i++)
    a[i].display(i);
    }
    
    template<class t>void sll<t>::display()
    {
    node *temp;
    temp=first;
    if(first==NULL)
    cout<<" Adjancent \n";
    else
    while(temp!=NULL)
    {
    cout<<temp->data;
    temp=temp->link;
    }
    }
    
    void graph::bft()
    {
    node *temp;
    int i,j;
    queue<int> b;
    int *visited;
    visited =new int[n];
    
    for(int i=0;i<n-1;i++)
    visited[i]=false;
    
    for(int i=0;i<=n-1;i++)
    {
    if(!visted[i])
    {
    b.insert(i);
    while(!b.isempty())
    {
    j=b.del();
    if(!visited[j])
    {
    cout<<j;
    visited[j]=false;
    for(temp=a[j].first;temp!=NULL;temp=temp->link)
    {
    if(!visited[temp->data])
    b.insert(temp->data);
    }
    }
    }
    }
    }
    }
    void graph::dft()
    {
    int *visited;int i;
    visited=new int[n];
    for(i=0;i<=n-1;i++)
    visited[i]=false;
    for(i=0;i<n-1;i++)
    {
    if(!visited[i])
    traverse(i,visited);
    }
    }
    void graph::travrse(int j,int visited[])
    {
    if(visited[j])
    {
    cout<<j;
    visited[j]=true;
    for(temp=a[j].first;temp!=NULL;temp=temp->link)
    {
    if(!visited[temp->data])
    traverse(temp->data,visited);
    }
    }
    }
    void menu()
    {
    cout<<"1.Print the Graph\n";
    cout<<"2.Display no of vertices and edges\n";
    cout<<"3.Display Degree of each vertex\n";
    cout<<"4.BFT\n";
    cout<<"5.DFT\n";
    cout<<"Exit\n";
    }
    
    
    
    main()
    {
    int ch;
    graph a;
    a.create();
    menu();
    cout<<"Enter Your Choice\n";
    cin>>ch;
    while(ch<6)
    {
    switch(ch)
    {
    case 1:
    		a.display();
    		break;
    case 2:
    		cout<<"No of vertices  :"<<a.nov();<<"\n";
    
    		cout<<"No of edges  :"<<a.noe();<<"\n";
    		break;
    case 3:
    		for(int i=0;i<=a.nov()-1;i++)
    		cout<<i<<"\t"<<a.degree(i)<<"\n";
    		break;
    case 4:
    		a.bft();
    		cout<<"\n";
    		break;
    
    case 5:
    		a.dft();
    		cout<<"\n";
    		break;
    
    }
    		menu();
    		cout<<"Enter Your Choice\n";
    		cin>>ch;
    }
    		getch();
    		return(0);
    }
     
    Last edited by a moderator: Nov 12, 2007

Share This Page