Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<list>
- using namespace std;
- class graph{
- public:
- int v;
- list<int> *adj;
- graph(int vertex){
- v=vertex;
- adj=new list<int>[v];
- }
- void AddEdge(int v1,int v2){
- adj[v1].push_back(v2);
- }
- };
- void DFSUtil(graph g,int start, bool visit[]){
- visit[start]=true;
- cout<<start<<" ";
- list<int>:: iterator ptr;
- for(ptr=g.adj[start].begin();ptr!=g.adj[start].end();ptr++){
- if(visit[*ptr]==false)
- DFSUtil(g,*ptr,visit);
- }
- }
- void DFS(graph g,int start){
- int vertex=g.v;
- bool visit[vertex];
- for(int i=0;i<vertex;i++)
- visit[i]=false;
- DFSUtil(g,start,visit);
- }
- int main(){
- graph g(4);
- g.AddEdge(0, 1);
- g.AddEdge(0, 2);
- g.AddEdge(1, 2);
- g.AddEdge(2, 0);
- g.AddEdge(2, 3);
- g.AddEdge(3, 3);
- cout << "Following is Depth First Traversal"
- " (starting from vertex 2) \n";
- DFS(g,2);
- return 0;
- }
- /* second method. DFS as member function of graph class
- class graph{
- public:
- int v;
- list<int> *adj;
- graph(int vertex){
- v=vertex;
- adj=new list<int>[v];
- }
- void AddEdge(int v1,int v2){
- adj[v1].push_back(v2);
- adj[v2].push_back(v1);
- }
- void DFSUtil(int start, bool visit[]){
- visit[start]=true;
- cout<<start<<" ";
- list<int> ::iterator i;
- for(i=adj[start].begin();i!=adj[start].end();i++){
- if(visit[*i]==false)
- DFSUtil(*i,visit);
- }
- }
- void DFS(int start){
- bool visit[v];
- for(int i=0;i<v;i++)
- visit[i]=false;
- DFSUtil(start,visit);
- }
- };
- */
Add Comment
Please, Sign In to add comment