SHARE
TWEET

Untitled

a guest Sep 16th, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // C++ program to print DFS traversal from
  2. // a given vertex in a given graph
  3. #include<iostream>
  4. #include<list>
  5. using namespace std;
  6.  
  7. // Graph class represents a directed graph
  8. // using adjacency list representation
  9. class Graph
  10. {
  11.     int V; // No. of vertices
  12.  
  13.     // Pointer to an array containing
  14.     // adjacency lists
  15.     list<int> *adj;
  16.  
  17.     // A recursive function used by DFS
  18.     void DFSUtil(int v, bool visited[]);
  19.   public:
  20.     Graph(int V); // Constructor
  21.  
  22.     // function to add an edge to graph
  23.     void addEdge(int v, int w);
  24.  
  25.     // DFS traversal of the vertices
  26.     // reachable from v
  27.     void DFS(int v);
  28. };
  29.  
  30. Graph::Graph(int V)
  31. {
  32.     this->V = V;
  33.     adj = new list<int>[V];
  34. }
  35.  
  36. void Graph::addEdge(int v, int w)
  37. {
  38.     adj[v].push_back(w); // Add w to v’s list.
  39. }
  40.  
  41. void Graph::DFSUtil(int v, bool visited[])
  42. {
  43.     // Mark the current node as visited and
  44.     // print it
  45.     visited[v] = true;
  46.     cout << v << " ";
  47.  
  48.     // Recur for all the vertices adjacent
  49.     // to this vertex
  50.     list<int>::iterator i;
  51.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  52.         if (!visited[*i])
  53.             DFSUtil(*i, visited);
  54. }
  55.  
  56. // DFS traversal of the vertices reachable from v.
  57. // It uses recursive DFSUtil()
  58. void Graph::DFS(int v)
  59. {
  60.     // Mark all the vertices as not visited
  61.     bool *visited = new bool[V];
  62.     for (int i = 0; i < V; i++)
  63.         visited[i] = false;
  64.  
  65.     // Call the recursive helper function
  66.     // to print DFS traversal
  67.     DFSUtil(v, visited);
  68. }
  69.  
  70. // Driver code
  71. int main()
  72. {
  73.     // Create a graph given in the above diagram
  74.     Graph g(4);
  75.     g.addEdge(0, 1);
  76.     g.addEdge(0, 2);
  77.     g.addEdge(1, 2);
  78.     g.addEdge(2, 0);
  79.     g.addEdge(2, 3);
  80.     g.addEdge(3, 3);
  81.  
  82.     cout << "Following is Depth First Traversal"
  83.             " (starting from vertex 2) \n";
  84.     g.DFS(2);
  85.   cout << endl;
  86.     return 0;
  87. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top