Depth First Search

DFS is an algorithm for traversing Graph data structures. It starts by selecting some arbitrary node and explores as far as possible along each edge before backtracking.

See it in action:

Code algorithm

For DFS, we utilise stack data structure to help with the operations.

type Node = {
  value: string;
  neighbours: Node[];
  hasVisited: boolean;
}

type Graph = {
  nodeList: Node[];
};

function dfs(graph: Graph): void {
  const stack = [];

  for (const node of graph.nodeList) {
    if (node.hasVisited) continue;

    stack.push(node);

    while (stack.length > 0) {
      const currentNode = stack.pop();
      if (currentNode.hasVisited) continue;

      currentNode.hasVisited = true;
      console.log(currentNode.value);

      currentNode.neighbours.forEach((neighbour) => {
        if (neighbour.hasVisited) return;
        stack.push(neighbour);
      });
    }
  }
}

For time and space complexity, check out my post on Run Time Complexity.