# Depth first traversal of graph ( DFS)

*Traversing a graph means visiting the nodes. In computer science the different ways of visiting nodes gives different results (sequence). In Depth first traversal of a graph , we visit the child node before visiting its sibling nodes. Visiting child nodes before its siblings nodes means , DFS explores its depth rather than breadth.*

*Note: All nodes must be visited only once.*

*Before applying DFS algorithm we need to represent the above graph in c/c++ program. There are two ways of representing this graph.*

* (1) Adjacency Matrix Representation, go to this link for more details
*

*(2) Adjacency list Representation, go to this link for more details*

*Here we will learn DFS of above graph by representing above graph as a adjacency list. The below figure shows adjacency list representation.
*

*Let node 0 is starting position, then do dfs.*

*(1) For depth first traversal , we use stack data structure. Now visit node 0 and push this node to the stack S and mark this node as visited. Here visited node is marked as green.*

(2) *After the first step, the 0th node has three children 1,4 and 2. we can visit to any child here. let visit node 4, push this node on stack S and mark this node visited.*

(3) *Now we are at 4, the children nodes of node 4 are 3 and 2. Now let visit node 3, push node 3 on stack S and mark this node visited.*

(4) *Now from node 3, we can not move to any other child node, because it has no child node. In this case we look at the top of stack S, and pop node 3 ( because it is visited node ). This is called backtracking.*

(5) *Now we are at the node 4, Now look at the every child node. They are 3 and 2. node 3 is already visited so we have to move to node 2. mark node 2 visited, push this node to stack S.*

(6) *Now we are at node 2. All the adjacent children of node 2 are 3 and 1. node 3 is visited node so we have to move to node 1. mark node 1 visited and push the node 1 on stack.*

(7) *Now we are at node 1. As there is no place to go from node 1, we pop off the node 1 from stack.*

(8) *Again look at the top of the node 2 on stack. This node is already visited and there is no child to visit, so we have to pop off this node from stack S.*

*(9) Now we are on node 4, as this node is already visited and there is no child to visit we have to pop off this node from stack S.*

(10) *Now we are at node 0, since it is already visited and there is no child to visit then we need to pop off this node from stack.*

(11)* Now the stack is empty. the empty stack shows that all nodes have been visited and hence depth first traversal has been finished. The result is 0 4 3 2 1.*

#include<iostream> #include<vector> #include<stack> using namespace std; #define N 5 // number of nodes class G { private: vector < int >adj[N]; bool visited[N]; stack < int >S; public: G () { // false is for new node and true is for visited node int i = 0; for (i; i < N; i++); visited[i] = false; } void addList (int u, int v); void dfs (int v); }; void G::addList (int u, int v) { adj[v].push_back (u); adj[u].push_back (v); } void G::dfs (int v) { //push node v on stack S.push (v); visited[v] = true; // mark it visited while (!S.empty ()) { int u = S.top (); // get node cout << u << " "; // print node S.pop (); // search for adjacent vertex of node u // if not visited,make it visited and push on stack for (int i = 0; i < adj[u].size (); i++) if (!visited[adj[u][i]]) { S.push (adj[u][i]); visited[adj[u][i]] = true; } } } int main () { G g; g.addList (0, 1); g.addList (0, 2); g.addList (4, 3); g.addList (0, 4); g.addList (4, 2); g.addList (2, 1); g.addList (2, 3); g.dfs (0); cout << endl; return 0; }

## Leave a Reply