Depth First Search in Graph

A depth-first traversal of a graph is similar to a depth-first traversal of a tree. The only difference in a graph is you can visit the same node twice through a different path. Let’s see the below example

Directed Graph

There are 2 possible ways to reach C. One via A and the other via D. So what we infer from here is a graph may contain cycles, so we might end up visiting the same nodes again and again. An ideal data structure to store the visited nodes without duplicates will be a Set.

In depth-first traversal, whenever we visit a Node, we visit all its neighbouring nodes before we proceed to the next. In the above graph when we start a DFS with node A, we add A to the visited set. Now we can go to either B or C as they both are A’s connected neighbours. If we visit B, we add it to the visited set which now contains[A, B]. As per DFS, we cannot go back to C, as we are not yet done visiting all the neighbours of B. So we visit D which is the next neighbour of B and add it to the set which looks like [A, B, D]. Now D has one connected neighbour which is C and we add to it the visited set[A, B, D, C]. Now finally when we go back to visit the left out neighbour of A which is C, it is already present in the visited set and yeah we are done with the depth-first traversal with our graph :)

DFS OUTPUT: A->B->D->C

Below is a code snippet of a depth-first approach using recursion in JAVA

public void depthFirstTraversal(String root) {
    Node node = nodes.get(root);
    if (node == null)
        return;
    depthFirstTraversal(node, new HashSet<Node>());
}
private void depthFirstTraversal(Node node, Set<Node> visitedNodes) {
    System.out.println(node.label);
    //Step-1: add the current node to the visited set
    visitedNodes.add(node);
    //Step-2: get all the neighbours of the current node
    for (Node connectedNode : adjacencyList.get(node)) {
        if (!visitedNodes.contains(connectedNode))
            //Step-3: recursive call to visit all its neigbours
            depthFirstTraversal(connectedNode, visitedNodes);
    }
}

Cheers :)