• API
• FAQ
• Tools
• Archive
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
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;
34. }
35.
36. void Graph::addEdge(int v, int w)
37. {
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;
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);