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:
- 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.
- 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:
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
- Number of Connected Components: Return number of connected components in a graph.
- Number of Islands: Return number groups of connected land 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.