DFS | kz-maxx

DFS деген не?

DFS — графты тереңдік бойынша обход жасау алгоритмі. Толық аты: Depth-First Search.

DFS мүмкін болғанша графтың ішіне терең кіріп кетеді. Егер ары қарай баратын жер болмаса, артқа қайтады.

вершинаға кірдік
бірінші бармаған көршіге өттік
тағы тереңірек кеттік
көрші қалмаса, артқа қайтамыз

DFS көбіне рекурсия арқылы жазылады. Бірақ stack арқылы да жазуға болады.

DFS негізгі идеясы

Бізде граф бар:

vector<int> g[N];

Және visited массиві бар:

bool used[N];

Егер біз v вершинасына кірсек, оны visited қыламыз:

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 тәртібі әртүрлі болуы мүмкін. Ол adjacency list ішіндегі көршілердің ретіне байланысты.

Обычный 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 массивін тазалаймыз:

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 v-ның parent-і болмаса
онда цикл бар

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).