Depth First Traversal

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

The main difference between DFS and BFS is queue and stack.

DFS-iterative (G, s):                                   
  let S be stack
  S.push( s )            //Inserting s in stack
  mark s as visited.

  while ( S is not empty):
      //Pop a vertex from stack to visit next
      v  =  S.top( )
     S.pop( )
     //Push all the neighbours of v in stack that are not visited   

    for all neighbours w of v in Graph G:
        if w is not visited :
             S.push( w )         
             mark w as visited

DFS-recursive(G, s):
  mark s as visited
  for all neighbours w of s in Graph G:
      if w is not visited:
          DFS-recursive(G, w)

Iterative Solution

void DFS(vector<list<int>> &adjList, int v) {
    auto size = adjList.size();
    vector<bool> visited(size, 0);
    stack<int> s;
    s.push(v);
    visited[v] = true;

    while (!s.empty()) {
        int n = s.top();
        s.pop();

        for (auto neighbor: adjList[n]) {
            if (visited[neighbor] == false) {
                s.push(neighbor);
            }
        }
        visited[n] = true;
    }
}

Recursive Solution

void DFSUtil(int v, vector<vector<int>> &adjList, bool *visited) {
    visited[v] = true;

    for (auto node: adjList[v]) {
        if (!visited[node]) {
            DFSUtil(node, adjList, visited);
        }
    }
}

void DFS(int v, vector<vector<int>> &adjList) {
    auto size = adjList.size();
    bool *visited = new bool[size];
    for (int i = 0; i < size; i++)
        visited[i] = false;

    DFSUtil(v, adjList, visited);
}