12.3 Применения обхода графа¶

В этом разделе рассмотрим, как алгоритмы обхода графа (DFS и BFS) позволяют решать классические задачи.

Будем считать, что граф неориентированный, если не указано иное.

1. Поиск компонент связности¶

Идея¶

Граф называется связным, если из любой вершины можно добраться до любой другой.

Если это не так — граф разбивается на компоненты связности.

Как найти компоненты¶

1. Заводим массив visited
2. Перебираем все вершины
3. Если вершина не посещена — запускаем DFS/BFS
4. Все достигнутые вершины — одна компонента

Пример¶

Граф:

graph LR
    A["1"] --- B["2"]
    B --- C["3"]
    D["4"] --- E["5"]

Компоненты:

• {1, 2, 3}
• {4, 5}

Код (DFS)¶

vector<int> adj[N];
bool used[N];

void dfs(int v) {
    used[v] = true;
    for (int u : adj[v]) {
        if (!used[u]) dfs(u);
    }
}

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

Сложность¶

O(n + m)

2. Проверка двудольности¶

Определение¶

Граф двудольный, если вершины можно покрасить в 2 цвета так, чтобы:

• соседние вершины имели разные цвета

Идея¶

1. Запускаем BFS/DFS
2. Красим вершину в цвет 0
3. Соседей — в 1
4. Их соседей — снова в 0
5. Если нашли конфликт — граф не двудольный

Пример¶

graph LR
    A["1"] --- B["2"]
    B --- C["3"]
    C --- D["4"]

Этот граф — двудольный.

А вот цикл из 3 вершин — нет.

Код¶

vector<int> adj[N];
int color[N]; // -1 = не покрашено

bool dfs(int v, int c) {
    color[v] = c;
    for (int u : adj[v]) {
        if (color[u] == -1) {
            if (!dfs(u, c ^ 1)) return false;
        } else if (color[u] == color[v]) {
            return false;
        }
    }
    return true;
}

Важное наблюдение¶

• Все деревья — двудольные
• Любой цикл нечётной длины ломает двудольность

3. Поиск циклов¶

Идея (для неориентированного графа)¶

Во время DFS:

Если мы пришли в уже посещённую вершину, которая не является родителем — найден цикл.

Пример¶

graph LR
    A["1"] --- B["2"]
    B --- C["3"]
    C --- A

Цикл: 1 → 2 → 3 → 1

Код¶

vector<int> adj[N];
bool used[N];

bool dfs(int v, int p) {
    used[v] = true;
    for (int u : adj[v]) {
        if (u == p) continue;
        if (used[u]) return true;
        if (dfs(u, v)) return true;
    }
    return false;
}

Альтернативная идея¶

Компонента с:

• c вершинами
• и ≥ c рёбрами

→ обязательно содержит цикл

4. Восстановление пути¶

Задача¶

Найти путь из вершины a в b

Идея¶

Во время BFS/DFS храним массив parent

• parent[u] = v — из какой вершины пришли

После достижения цели — восстанавливаем путь назад

Пример¶

graph LR
    A[1] --> B[2]
    B --> C[3]
    C --> D[4]

Путь от 1 к 4: 1 → 2 → 3 → 4

Код (BFS)¶

queue<int> q;
vector<int> adj[N];
bool used[N];
int parent[N];

void bfs(int start) {
    q.push(start);
    used[start] = true;
    parent[start] = -1;

    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) {
            if (!used[u]) {
                used[u] = true;
                parent[u] = v;
                q.push(u);
            }
        }
    }
}

Восстановление пути¶

vector<int> path;
for (int v = target; v != -1; v = parent[v]) {
    path.push_back(v);
}
reverse(path.begin(), path.end());

Важно¶

• BFS → кратчайший путь (в невзвешенном графе)
• DFS → просто какой-то путь

Итог¶

Обход графа — это базовый инструмент, который позволяет:

• находить компоненты связности
• проверять двудольность
• находить циклы
• восстанавливать пути

И почти все задачи на графы начинаются именно с этих техник.