Gayan Hewa
PHANTOM DEV

PHANTOM DEV

Depth First Search (Part 1) - Iterative approach

Depth First Search (Part 1) - Iterative approach

Subscribe to my newsletter and never miss my upcoming articles

Depth First Search Algorithm

Depth first search, famously known for its acronym DFS. It is a popular traversal algorithm for Graphs and Tree Data Structures.

DFS vs BFS.png

For an example, if we are exploring for valid paths from A --> F DFS algorithm will traverse through each branch until it reaches the leaf node in that branch before exploring the next branch. So in this case, the exploration would happen in the following order (If the first traversal is to B).

Goal : Find out all the paths to a leaf node from a given node

DFS-exploring-path.png

How do we approach this, every time we need to do a depth first search, we are going to have a starting node. Some problems will consist of a ending node or you would just have to print out paths or nodes that satisfy a certain condition or a constraint.

Below are the steps that we will follow to get all available paths to leaf nodes.

psuedocode.png

In this example we continue to repeat visiting the node and then looking at the neighbours and if the node has no neighbours that means we have found a valid path. This will repeat until all the nodes have traversed.

When we translate this to code, the key thing here is Depth First Search to work we need to keep a track of the neighbours. For the business rules to be applied against these nodes we need to process them in a certain order. For an example:

Visit A -> B -> E -> G

Visit A -> C

Visit A -> D -> F

If you look closely to the flow of the data, we process the element that we are visiting and then move on to the most recently found neighbour. This is a common concept known as LIFO or Last In First Out. In programming stack implement the LIFO concept. And this is the data structure that is going to help us navigate Depth First Search.

Let's look at a simple implementation using Javascript.

const dfs = (graph, start)  => {
    // We can use a simple array data structure.
    // To operate is as a stack we use the push and pop
    // methods on the Array object.
    // We initialize the stack with the starting node.
    const stack = [start];

    while(stack.length > 0) {
        // First thing we do is visit the node in the stack.
        // We do this buy taking it out of the stack.
        const visitingNode = stack.pop();

        // Look what we have here.
        // So if the visitingNode has no neighbours that means
        // You have found your self at the leaf node.
        if (graph[visitingNode] && graph[visitingNode].length === 0) {
            console.log(`Visiting the leaf node ${visitingNode}`);
        }
        // Next up, is to check who the neighbours are
        // We can find the neighbours in graph adjacency list
        // graph[node]
        for (let neighbour of graph[visitingNode]) {
            // We need to visit each of these neighbours
            // So we are going to push them up to the stack.
            stack.push(neighbour);
        }
    }
}

const graph = {
    "A": ["B", "C", "D"],
    "B" : ["E"],
    "C" : [],
    "D" : ["F"],
    "E" : ["G"],
    "F" : [],
    "G" : [],
}

dfs(graph, 'A');

The code snippet above will traverse the graph from the start point we've given until it reaches leaf nodes and then print the leaf node. This is one step close to our goal. In order to get close to our final goal, we need to modify the code a bit, we need to keep a track of each visited node we have travelled before we reach the leaf node to have the full path. There are different ways of going about this, for this example I am going to use a more obvious approach help understand it better.

'use strict';

const dfs = (graph, start)  => {
    // Changing the value pushed to the stack to hold the node and the path
    // Node is the vertex being visited
    // Path is every node we have visited.
    const stack = [{
        node: start,
        path: [],
    }];

    while(stack.length > 0) {
        const current = stack.pop();
        const visitingNode = current.node;
        const path = current.path;

        // Update the current path to include the visited node.
        path.push(visitingNode);

        // Exist condition is the same as before.
        // But now we have the valid paths when we reach the end.
        if (graph[visitingNode] && graph[visitingNode].length === 0) {
            console.log(path.join(' -> '));
        }

        for (let neighbour of graph[visitingNode]) {

            // Pushing an object to the stack.
            // We are premptively adding the
            stack.push({
                node: neighbour,
                path: [...path]
            });
        }
    }
}

const graph = {
    "A": ["B", "C", "D"],
    "B" : ["E"],
    "C" : [],
    "D" : ["F"],
    "E" : ["G"],
    "F" : [],
    "G" : [],
}

dfs(graph, 'A');

example-output-dfs-traversal.png

Key learnings from this is, if you are ever in a situation where you have to implement depth first traversal, you will need to implement it using a stack data structure.

The code here is a lot of lines, especially because implementing depth first search using iterative approach requires a considerable amount of lines.

In the next part of this article we will discuss how to implement this using recursion and the call stack. Because DFS requires a stack data structure, the call "stack" is a natural candidate. This would generally mean less code. But when you are new to recursion its a bit hard to wrap your head around a recursive solution. It's easier to understand the iterative solution and then refactor into a recursive solution.

If you are really keen, you can try out the questions in the section below before learning the Recursive method. This will help you understand how things work in an iterative approach.

Resources

Example problem sets from leetcode that will help you really help you understand this concepts.

 
Share this