0Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Depth First Traversal of the following graph is 2, 0, 1, 3.
Following are implementations of simple Depth First Traversal. The C++ implementation uses adjacency list representation of graphs. STL‘s list container is used to store lists of adjacent nodes.
First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Depth First Traversal of the following graph is 2, 0, 1, 3.
Following are implementations of simple Depth First Traversal. The C++ implementation uses adjacency list representation of graphs. STL‘s list container is used to store lists of adjacent nodes.
// C++ program to print DFS traversal from// a given vertex in a given graph#include#includeusing namespace std;// Graph class represents a directed graph// using adjacency list representationclass Graph{ int V; // No. of vertices // Pointer to an array containing // adjacency lists list<int> *adj; // A recursive function used by DFS void DFSUtil(int v, bool visited[]);public: Graph(int V); // Constructor // function to add an edge to graph void addEdge(int v, int w); // DFS traversal of the vertices // reachable from v void DFS(int v);};Graph::Graph(int V){ this->V = V; adj = new list<int>[V];}void Graph::addEdge(int v, int w){ adj[v].push_back(w); // Add w to v’s list.}void Graph::DFSUtil(int v, bool visited[]){ // Mark the current node as visited and // print it visited[v] = true; cout << v << " "; // Recur for all the vertices adjacent // to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFSUtil(*i, visited);}// DFS traversal of the vertices reachable from v.// It uses recursive DFSUtil()void Graph::DFS(int v){ // Mark all the vertices as not visited bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function // to print DFS traversal DFSUtil(v, visited);}int main(){ // Create a graph given in the above diagram 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"; g.DFS(2); return 0;}
