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.

Depth first traversal of graph 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.

Depth first traversal of graph 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.

Depth first traversal of graph (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.

Depth first traversal of graph (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.

Depth first traversal of graph (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.

Depth first traversal of graph (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.

Depth first traversal of graph (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.

Depth first traversal of graph (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.

Depth first traversal of graph (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.

 Depth first traversal of graph

(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.

Depth first traversal of graph

(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.

Depth first traversal of graph

(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;
}



Related Contents to follow