Coding Pattern:

Graph Depth First Search

Note

🛑 We strongly suggest familiarizing yourself with graphs if you haven't already. Otherwise, this section will be very confusing :)

Overview

Graph depth first search or more commonly known as just depth first search (DFS), is the most straightforward way to traverse a graph.

DFS is used to solve graph traversal problems. In particular, it excels in the following traversal categories:

  1. Validation Problems involve "finding" if a certain condition in a graph is true or not. Most of the time it means checking if a node exists in the graph or if two nodes are connected.
  2. Path Problems are more complex cases where you would checking whether a certain condition in a graph is true or not, in addition to returning the path to a node. For example, return the nodes of a cycle (if one exists) in a graph.

Note

A lot of problems in depth first search can be solved using breadth first search! However, depth first search should be favored in interviews due to its simplicity and versatility. Believe it or not, backtracking pattern is DFS used in a particular way.

Pattern concept

Let's go over an example of a basic graph validation problem:

Graph Depth First Search Slide
1 of 19

Solution templates

There are two solution templates for implementing depth-first search in a graph, depending on what the question asks for:

  • Validation problems: you need to verify certain conditions
  • Path problems: you need to verify certain conditions AND return the actual path taken

Validation Problem

An example validation problem: Return if node 0 is connected to node 4.

Path Problem

An example path problem: If node 0 is connected to node 4, return the path.

Note

The code solution can vary slightly by whether you choose to build a directed graph or undirected graph. You can decide this by asking yourself: is there a dependency between nodes in the graph?

How to identify

Does the problem involve any of these?

  • Find number of connected components in a graph
  • Exploring paths or connections between nodes in a graph
    • Return whether node A is connected to node B.
    • Return the path from node A to node B if they're connected.
    • Pacific Atlantic Water Flow: Return which cells on the grid can have water flowing to certain borders of the grid.
    • Course Schedule: Determine if a valid order exists between courses.
  • Exploring combinations that satisfy a condition (covered later)

Note

Generally, the time complexity of depth first search is O(n + e) where n is the number of nodes and e is the number of edges in the graph. When you traverse the graph, you visit each node and edge exactly once.