Depth first traversal of graph

Depth first traversal of a graph

In the last post, we discussed how to represent a graph in a programmatic way using adjacency matrix and adjacency list representation. Let’s discuss now, how to traverse a graph. There are two ways to traverse a graph: Depth First traversal, commonly called DFS and Breadth First traversal, commonly called as BFS.

What is Depth First Traversal (DFS) ?

Depth First search or traversal is a technique in which we go as deep in the graph as possible and explore nodes, that is we move down the graph from one node to another till we can. Once we reach a node where we cannot go further down, we backtrack and move to node one before and so on.
A depth-first traversal of a graph is a very good example to understand how backtracking works.

Let’s see how do we traverse a graph depth first.

  1. Start with node u.
  2. If u is already visited, return.
  3. Mark visited[u] = true.
  4. For all neighbors v of u.
  5. v is now new u, so u=v and go back to step 2
  6. When all neighbors are processed, backtrack to parent of current u.

When we reach at start node S again and there is no edge to be explored at S, that would be the end of traversal.

Let’s take an example and see how it works. Given the graph below, let’s trace how depth first search will go.
depth first traversal of a graph

We start with node(1), and mark it as visited.

depth first traversal

Now, we pick neighbor of node(1), and go down to node(2) and mar it as visited too.
depth first traversal

Next, we move to the neighbor of node(2), which is node(3).

After marking node(3) visited, we move to node(4).
depth first search in graph

Next, we move to node(6). At this point, we have no neighbors to visit from node(6). So, we start backtracking.
depth first traversal

At node(2), we have another neighbor called node(4), however, node(4) is already visited when we went deep from node(3). So nothing happens, we move further back. At node(1), we have neighbor node(5).
Since node(5) is not visited, we mark it as visited.
depth-first-traversal

At this point, there is no node with neighbor not traversed, so end of depth-first traversal.

Depth first traversal : implementation

package com.company.Graphs;

import java.util.ArrayList;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyMatrix {
    private boolean [][] G;
    private boolean isDirected;

    public AdjacencyMatrix(int numNodes, boolean isDirected){
        this.G  = new boolean[numNodes+1][numNodes+1];
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){
        this.G[start][dest] = true;
        if(!isDirected){
            this.G[dest][start] = true;
        }
    }

    public boolean isEdge(int start, int dest){
        return this.G[start][dest];
    }

    private void DFS(int node, boolean[] visited, 
                     ArrayList<Integer> traversal){
        if(!visited[node]){
            traversal.add(node);
            visited[node] = true;

            //Complexity of this loop is O(V * E)
            for(int i=1; i< this.G[1].length; i++){
                if(this.G[node][i]){
                    //This will be called E times (number of edges)
                    DFS(i, visited, traversal);
                }
            }
        }
    }
    public ArrayList<Integer> depthFirstTraversal(){

        boolean[] visited = new boolean[this.G.length];
        ArrayList<Integer> traversal = new ArrayList<>();

        DFS(1, visited, traversal);

        System.out.println(traversal);
        return traversal;

    }
}

The complexity of the above implementation is O(V * E).

Depth first traversal when the graph is represented using adjacency list.

package com.company.Graphs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyList {
    private Map<Integer, ArrayList<Integer>> G;
    boolean isDirected;

    public AdjacencyList(boolean isDirected){
        this.G = new HashMap<>();
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){

        if(this.G.containsKey(start)){
            this.G.get(start).add(dest);
        }else{
            this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
        }

        //In case graph is undirected
        if(!this.isDirected) {
            if (this.G.containsKey(dest)) {
                this.G.get(dest).add(start);
            } else {
                this.G.put(dest, new ArrayList<>(Arrays.asList(start)));
            }
        }
    }

    public boolean isEdge(int start, int dest){
        if(this.G.containsKey(start)){
            return this.G.get(start).contains(dest);
        }

        return false;
    }


    private void DFS(int node, boolean[] visited, 
                     ArrayList<Integer> traversal){
        if(!visited[node]){
            traversal.add(node);
            visited[node] = true;

            this.G.get(node).forEach(v -> DFS(v, visited, traversal));
        }
    }
    public ArrayList<Integer> depthFirstTraversal(){

        boolean[] visited = new boolean[this.G.size()+1];
        ArrayList<Integer> traversal = new ArrayList<>();

        DFS(1, visited, traversal);

        System.out.println(traversal);
        return traversal;

    }
}

The complexity of the above implementation is O(V + E).

Both above implementations are recursive implementation. We can use a stack to replace recursion. Algorithm remains the same, for each node visited, put all the adjacent nodes into the stack. Take next node from the stack, mark it as visited and put all the adjacent nodes to stack. Repeat the process till stack is not empty.

public ArrayList<Integer> depthFirstTraversalNonRecursive(){

        boolean[] visited = new boolean[this.G.length];
        ArrayList<Integer> traversal = new ArrayList<>();

        Stack s = new Stack();
        s.push(1);
        visited[1] = true;

        while(!s.isEmpty()){
            int currentNode = (int)s.pop();
            traversal.add(currentNode);

            for(int i=1; i< this.G[1].length; i++){
                if(this.G[currentNode][i] && !visited[i]){
                    s.push(i);
                    visited[i] = true;
                }
            }
        }

        System.out.println(traversal);
        return traversal;

    }

This implementation of dept first traversal or DFS works only if the graph has only one connected component. If there are multiple connected components in the graph, this will not work. For example, above implementation will not work for below graph.

It can be easily fixed. All we need to do is that we try to start DFS from each node of the graph. Check if a node is not already visited for earlier DFS run, then start another DFS from that node. Below is the changed code.

  private void DFS(int node, boolean[] visited, 
                   ArrayList<Integer> traversal){
        if(!visited[node]){
            traversal.add(node);
            visited[node] = true;

            for(int i=1; i< this.G[1].length; i++){
                if(this.G[node][i]){
                    DFS(i, visited, traversal);
                }
            }
        }
    }
    public ArrayList<Integer> depthFirstTraversal(){

        boolean[] visited = new boolean[this.G.length];
        ArrayList<Integer> traversal = new ArrayList<>();

        for(int i=1; i<this.G.length; i++) {
            if(!visited[i])
                DFS(i, visited, traversal);
        }

        System.out.println(traversal);
        return traversal;
    }

Applications of DFS

  1. Minimum spanning tree
  2. To check if graph has a cycle.
  3. Topological sorting
  4. To find strongly connected components of graph
  5. To find bridges in graph

Please share if there something wrong or missing. Please reach out to communications@algorithmsandme.com if you need personalized coaching for an interview.