DFS | kz-maxx

Что такое DFS?

DFS — это обход графа в глубину. Полное название: Depth-First Search.

DFS идет как можно глубже по графу. Если дальше идти нельзя, он возвращается назад.

зашли в вершину
пошли в первого непосещенного соседа
снова пошли глубже
если соседей больше нет, возвращаемся назад

DFS часто пишут через рекурсию. Но можно написать и через stack.

Главная идея DFS

У нас есть граф:

vector<int> g[N];

И массив посещенных вершин:

bool used[N];

Если мы зашли в вершину v, то сразу отмечаем ее:

used[v] = true;

Потом смотрим всех соседей:

for (int to : g[v]) {
    if (!used[to]) {
        dfs(to);
    }
}

Если сосед еще не посещен, запускаем DFS от него.

Пример обхода

Пусть есть граф:

1 -- 2 -- 4
| |
3 -- 5

Запускаем DFS из вершины 1.

dfs(1)
идем в 2
идем в 4
возвращаемся в 2
идем в 5
идем в 3

Порядок может быть разным. Он зависит от порядка вершин в списке смежности.

Обычный DFS

void dfs(int v) {
    used[v] = true;

    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

Здесь:

v — текущая вершина
used[v] — были ли мы в вершине
to — сосед вершины v
dfs(to) — идем глубже

Задача 1: проверить достижимость

Дан неориентированный граф. Нужно проверить, можно ли дойти из вершины s в вершину t.

Input

Output

YES

Полная реализация DFS

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

const int N = 100010;

int n, m, s, t;
vector<int> g[N];
bool used[N];

void dfs(int v) {
    used[v] = true;

    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(s);

    if (used[t]) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

Компоненты связности

Компонента связности — это часть графа, где из каждой вершины можно дойти до каждой другой.

DFS очень удобно использовать для подсчета компонент.

идем по всем вершинам
если вершина еще не visited
значит нашли новую компоненту
запускаем dfs от нее

int cnt = 0;

for (int i = 1; i <= n; i++) {
    if (!used[i]) {
        cnt++;
        dfs(i);
    }
}

Задача 2: количество компонент связности

Дан неориентированный граф. Нужно найти количество компонент связности.

Input

Output

Компоненты:

1 2 3
4
5 6

Полная реализация компонент

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

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];

void dfs(int v) {
    used[v] = true;

    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    int cnt = 0;

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            cnt++;
            dfs(i);
        }
    }

    cout << cnt;

    return 0;
}

Вывести все компоненты

Можно не только посчитать компоненты, но и вывести вершины каждой компоненты.

vector<int> component;

void dfs(int v) {
    used[v] = true;
    component.push_back(v);

    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

Перед каждым новым DFS очищаем массив:

component.clear();
dfs(i);

Полная реализация вывода компонент

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

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
vector<int> component;

void dfs(int v) {
    used[v] = true;
    component.push_back(v);

    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            component.clear();
            dfs(i);

            for (int x : component) {
                cout << x << ' ';
            }

            cout << '\n';
        }
    }

    return 0;
}

DFS и цикл в неориентированном графе

DFS можно использовать, чтобы проверить, есть ли цикл в неориентированном графе.

Идея:

если идем из v в to
и to уже visited
и to не является parent вершины v
значит нашли цикл

bool hasCycle = false;

void dfs(int v, int p) {
    used[v] = true;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            hasCycle = true;
            continue;
        }

        dfs(to, v);
    }
}

Полная реализация поиска цикла

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

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
bool hasCycle = false;

void dfs(int v, int p) {
    used[v] = true;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            hasCycle = true;
            continue;
        }

        dfs(to, v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    if (hasCycle) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

DFS в матрице

DFS можно использовать не только в графе, но и в матрице. Например, чтобы посчитать количество областей.

Пусть:

. — пустая клетка
# — стена

Из клетки можно идти в 4 стороны:

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

Задача 3: количество областей в матрице

Дана матрица. Нужно посчитать количество областей из точек ..

Input

4 5
..#..
..#..
####.
...#.

Output

Полная реализация DFS в матрице

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

const int N = 1010;

int n, m;
char a[N][N];
bool used[N][N];

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

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

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

        if (nx < 1 || nx > n || ny < 1 || ny > m) {
            continue;
        }

        if (a[nx][ny] == '#') {
            continue;
        }

        if (used[nx][ny]) {
            continue;
        }

        dfs(nx, ny);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    int cnt = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '.' && !used[i][j]) {
                cnt++;
                dfs(i, j);
            }
        }
    }

    cout << cnt;

    return 0;
}

Когда использовать DFS?

Нужно обойти все вершины графа
Нужно проверить достижимость
Нужно найти компоненты связности
Нужно найти цикл
Нужно работать с деревом
Нужно обойти клетки матрицы
Нужна топологическая сортировка

DFS vs BFS

Алгоритм	Как идет	Структура	Где удобно
DFS	в глубину	recursion / stack	компоненты, дерево, цикл
BFS	по слоям	queue	shortest path в невзвешенном графе

Асимптотика

Случай	Время	Память
Граф	O(n + m)	O(n + m)
Матрица n × m	O(n · m)	O(n · m)

В графе DFS проходит каждую вершину и каждое ребро максимум несколько раз. Поэтому время работы — O(n + m).