Depth-First Search (DFS)

19 Oct 2024

1. Introduction

Depth-First Search (DFS) traverses states by going as far as possible along one path before returning. At each position, it chooses an untried path and continues searching. When that path cannot continue, it goes back to the previous step and tries another choice.

DFS is often written with recursion. One function call represents reaching the current state. Inside the function, we enumerate every possible next step and recursively enter the next state. When a search finishes, the program returns to the previous recursive call and continues enumerating choices. This returning process is called backtracking.

DFS is commonly used for permutations, combinations, mazes, and connected components in grids. The meaning of a “next step” changes from problem to problem, but the overall structure is similar: describe the current state, decide the stopping condition, enumerate valid choices, and search recursively.

2. The Basic Pattern for Grid DFS

In a two-dimensional grid, a cell is usually represented by (x, y). If movement is allowed only up, down, left, and right, two arrays can represent the four directions:

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

Before moving from (x, y) to a neighboring cell, check the following in order:

The new coordinates are still inside the grid.
The cell can be entered.
The cell has not been visited before.

Mark a cell as visited as soon as it is reached. Otherwise, the search may move back and forth between neighboring cells forever, causing infinite recursion. In problems that only ask whether a region exists or how many connected regions there are, the mark does not need to be removed, because we do not need to start from that cell again.

3. Example: Luogu P1451: Cell Count

The problem gives a grid containing 0 and non-0 characters. Non-0 cells that are adjacent up, down, left, or right belong to the same cell group. The task is to count the number of groups.

Scan the grid from top to bottom and from left to right. Whenever an unvisited non-0 cell is found, increase the answer by one and start DFS from it. That DFS marks every cell connected to it, so the same group is never counted twice.

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int m, n;
char grid[N][N];
bool visited[N][N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void dfs(int x, int y) {
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
        if (grid[nx][ny] == '0') continue;
        if (visited[nx][ny]) continue;

        dfs(nx, ny);
    }
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        cin >> grid[i];
    }

    int answer = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != '0' && !visited[i][j]) {
                answer++;
                dfs(i, j);
            }
        }
    }

    cout << answer;
    return 0;
}

For example, if the grid has three separate non-0 regions, the outer loops find a new unvisited cell three times, so the answer is 3. Each non-0 cell is visited by DFS at most once, so the time complexity is O(mn), where m and n are the number of rows and columns.

The key to DFS is to identify what one state represents and which next states are reachable. In a grid problem, the state is the current coordinate; in a permutation problem, it can be the number of positions already filled. Once the state, stopping condition, and visited markers are clear, many search problems can be expressed naturally with recursion.

Depth-First Search (DFS)

Related Posts