Depth First Search (DFS)

In a Nutshell

• Typically used on graphs or trees represented as adjacency lists or hash maps.

• Explores a tree/graph data structure as deep as possible before backtracking.

• Useful when you want to check if a path exists, not necessarily the shortest one.

• Ideal for flood fill tasks — marking all connected nodes with a shared property.

• Common in backtracking problems like puzzles or generating combinations.

Time Complexity

Worst case: visit each node and explore every edge. Thus, our time complexity is O(|V| + |E|), the number of vertices plus the number of edges.

Procedure

Above is an animation of a DFS algorithm traversing a tree. Here is an example code in python:

def dfs(graph, node):
    visited = []
    stack = deque()

    visited.append(node)
    stack.append(node)

    while stack:
        s = stack.pop()
        for n in reversed(graph[s]):
            if n not in visited:
                visited.append(n)
                stack.append(n)

1. Create an empty list visited and a stack and append the starting node to both

2. Iterate over the nodes in the stack

3. Reverse the neighbour list so we have last in first out (LIFO)

4. If the neighbours aren’t in visited add them to the stack

The stack is created using deque which is a double-ended queue:

• You can append and pop from both ends in O(1) time.

• It’s faster than using a regular list when you need a queue or stack behavior.

Let’s apply DFS to a problem.

Leetcode Problem 200. Number of Islands [Medium]

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

DFS Python [Time: O(Rows*Cols), Space: O(Rows*Cols)]

def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            # Boundary check and skip water or visited cells
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
                return
            # Mark current cell as visited
            grid[r][c] = '0'
            # Explore neighbors in 4 directions
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    dfs(r, c)
                    count += 1

        return count

This is an example of flood-fill. In this problem we are given a list of lists, which might look like:

grid = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
]

Explanation

• Set the rows = length of grid

• Set the columns = length of first list in grid grid[0]

• The recursive dfs function explores neighbours in each of the four directions. We ignore water cells and cells outside the boundaries of the grid.

• We mark visited cells as 0

• We traverse the graph and begin a search every time we encounter 1

Why can we mark visited land to be 0 (the same as water)?

We only begin searches if we encounter land (1 in the grid). We increase the number of islands count any time this occurs and then effectively “delete” all of the connected land with our DFS so all the connected land counts as one island. Setting the visited land to be 0 means our loop will now skip over it without the need for a separate visited array, optimising space complexity.

C++ Version

void dfs(vector<vector<char>>& grid, int r, int c) {
        int rows = grid.size();
        int cols = grid[0].size();

        // Boundary and visited/water check
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != '1') {
            return;
        }

        // Mark current cell as visited by setting to '0'
        grid[r][c] = '0';

        // Explore neighbors
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();
        int count = 0;

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == '1') {
                    dfs(grid, r, c);
                    ++count;
                }
            }
        }

        return count;
    }