Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   DFS and BFS in Graph (http://www.go4expert.com/forums/dfs-bfs-graph-t7256/)

vkiransrinivas 12Nov2007 10:24

DFS and BFS in Graph
 
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);
}



All times are GMT +5.5. The time now is 03:18.