How to Implement DFS? | Part 3

By Prajwal Haniya

Techletter #27 | May 21, 2023

The DFS is implemented using stack. So let’s first implement stack in JavaScript

class Stack {
    constructor() {
        this.arr = [];
    }

    push(element) {
        this.arr.push(element);
    }

    pop() {
        if (this.arr.length == 0) {
            return "No elements present to pop";
        }
        this.arr.pop();
    }

    peek() {
        if (this.arr.length == 0) {
            return "No elements present";
        }
        return this.arr[this.arr.length - 1];
    }

    isEmpty() {
        return this.arr.length == 0;
    }
}

const stack = new Stack();
stack.push(1);
console.log(stack.peek());
stack.pop();
console.log(stack.peek());

The above code implements the stack. Now, by making use of this data structure let us understand how to implement DFS

As the name suggests it traverses in depth first manner.

class Node {
    constructor(value) {
        this.value = value;
        this.adjacentNodes = [];
        this.visited = false;
    }

    addAdjacentNode(node) {
        this.adjacentNodes.push(node);
    }

    getAdjacentNodes() {
        return this.adjacentNodes;
    }
    
    markVisited() {
        this.visited = true;
    }

    isVisited() {
        return this.visited;
    }
}

This is the class that creates the node along with other methods for each specific node. It also keeps track that the node is visited or not just with a boolean. You don’t need to create a map as in BFS.

Let’s continue…

function DFS(startNode) {
    const stack = [];
    stack.push(startNode);
    
    while (stack.length > 0) {
        const currentNode = stack.pop();
        currentNode.markVisited()
        console.log(currentNode.value);

        const adjacentNodes = currentNode.getAdjacentNodes();
        for (const adjacentNode of adjacentNodes) {
            if (!adjacentNode.isVisited()) {
                stack.push(adjacentNode);
            }
        }
    }
}

You can test the above code:

// Create nodes
const nodeA = new Node("A");
const nodeB = new Node("B");
const nodeC = new Node("C");
const nodeD = new Node("D");
const nodeE = new Node("E");
const nodeF = new Node("F");
const nodeG = new Node("G");

// Build the graph connections
nodeA.addAdjacentNode(nodeB);
nodeA.addAdjacentNode(nodeE);
nodeB.addAdjacentNode(nodeC)
nodeB.addAdjacentNode(nodeD);
nodeE.addAdjacentNode(nodeF);
nodeE.addAdjacentNode(nodeG)

// Perform DFS starting from node A
DFS(nodeA); // A E G F B D C