Depth-First Search | Skilled.dev
Learn

Depth-First Search

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...
Credit: VisuAlgo
Pros 🔥
  • Less memory used
    Paths tend to contain less nodes, so it will be better with memory (good if tree is wider than it is deep)
  • Determine if a path exists
    It is efficient in finding if a path between a source and target exists
Cons 🤕
  • Deep graphs are slow
    It can get slow if the graph is deep and doesn't traverse a node's closest neighbors quickly (bad if tree is deeper than it is wide)

Depth-first search (DFS) follows paths to their end before moving on to the next path. It goes deep before it goes wide.

To implement DFS, we use a stack data structure. With recursive DFS, our stack is just the function call stack, but if we do it iteratively, we create an actual stack data structure in our code. A stack is used because we continue to add items to it until we reach the end of a path. Then we pop them off until we return to the beginning of the path and perform the operation again.

DFS is often assumed to require less memory than BFS because the width of a path tends to have more nodes than its height. DFS only stores a path whereas BFS must store all of a node's children. Because of this assumption on less memory, DFS is typically the preferred choice.

To implement DFS, we will use a graph node that stores data and its edges. The edges variable is just an array of pointers to its sibling nodes. We will also assume our graph is undirected.

Nodes will take the following form:

class GraphNode {
  constructor(data) {
    this.data = data;
    this.edges = [];
  }
}

Because there can be cycles in graphs or multiple nodes that share an edge, we need to track if we have visited a given item. If not, we could traverse our graph infinitely.

The iterative DFS is give below:

const iterativeDepthFirstSearch = (startingNode) => {
  // Init our stack and set of visited nodes
  const dfsStack = [startingNode];
  const visitedNodes = new Set();

  visitedNodes.add(startingNode);

  while (dfsStack.length > 0) {
    const node = dfsStack.pop();

    visit(node);

    node.edges.forEach(childNode => {
      if (!visitedNodes.has(childNode)) {
        dfsStack.push(childNode);
        visitedNodes.add(childNode);
      }
    });
  }
};

In the iterative solution, we maintain our stack and track if have visited a node. My using a stack, we are always traversing from the most recently added item which keeps us moving towards the end of any given path.

The recursive DFS solution is below. In this case, the stack used to store nodes is actually the calls stack.

// Create a helper function to add visitedNodes to the signature
const dfs = (currentNode, visitedNodes) => {
  // Use node value for the question
  visit(currentNode);

  visitedNodes.add(currentNode);

  currentNode.edges.forEach(childNode => {
    if (!visitedNodes.has(childNode)) {
      dfs(childNode, visitedNodes);
    }
  });
}

const recursiveDepthFirstSearch = startingNode => {
  // Init our stack and set of visited nodes
  const visitedNodes = new Set();
  dfs(startingNode, visitedNodes);
};
Prev
Graphs
Next
Breadth-First Search
Loading...

Table of Contents