jain12

DFS in graph

Apr 21st, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include<iostream>
  2. #include<list>
  3. using namespace std;
  4.  
  5. class graph{
  6.   public:
  7.       int v;
  8.       list<int> *adj;
  9.       graph(int vertex){
  10.         v=vertex;
  11.         adj=new list<int>[v];
  12.         }
  13.       void AddEdge(int v1,int v2){
  14.         adj[v1].push_back(v2);
  15.         }
  16.   };
  17.  
  18. void DFSUtil(graph g,int start, bool visit[]){
  19.   visit[start]=true;
  20.   cout<<start<<" ";
  21.   list<int>:: iterator ptr;
  22.   for(ptr=g.adj[start].begin();ptr!=g.adj[start].end();ptr++){
  23.     if(visit[*ptr]==false)
  24.         DFSUtil(g,*ptr,visit);
  25.      }
  26.   }
  27.  
  28. void DFS(graph g,int start){
  29.   int vertex=g.v;
  30.   bool visit[vertex];
  31.   for(int i=0;i<vertex;i++)
  32.     visit[i]=false;
  33.   DFSUtil(g,start,visit);
  34.   }
  35.  
  36. int main(){
  37.     graph g(4);
  38.     g.AddEdge(0, 1);
  39.     g.AddEdge(0, 2);
  40.     g.AddEdge(1, 2);
  41.     g.AddEdge(2, 0);
  42.     g.AddEdge(2, 3);
  43.     g.AddEdge(3, 3);
  44.     cout << "Following is Depth First Traversal"
  45.             " (starting from vertex 2) \n";
  46.     DFS(g,2);
  47.     return 0;
  48.     }
  49.  
  50. /*  second method. DFS as member function of graph class
  51. class graph{
  52.   public:
  53.       int v;
  54.       list<int> *adj;
  55.       graph(int vertex){
  56.         v=vertex;
  57.         adj=new list<int>[v];
  58.         }
  59.       void AddEdge(int v1,int v2){
  60.         adj[v1].push_back(v2);
  61.         adj[v2].push_back(v1);
  62.         }
  63.  
  64.       void DFSUtil(int start, bool visit[]){
  65.          visit[start]=true;
  66.          cout<<start<<" ";
  67.          list<int> ::iterator i;
  68.          for(i=adj[start].begin();i!=adj[start].end();i++){
  69.              if(visit[*i]==false)
  70.                  DFSUtil(*i,visit);
  71.              }
  72.           }
  73.  
  74.       void DFS(int start){
  75.            bool visit[v];
  76.            for(int i=0;i<v;i++)
  77.                 visit[i]=false;
  78.            DFSUtil(start,visit);
  79.            }  
  80.  
  81.   };
  82. */
Add Comment
Please, Sign In to add comment