Обходы графа: поиск в глубину и поиск в ширину

Модуль "Графы" • урок 2 из 4 • ~15 минут

Поиск в глубину (Depth-First Search, DFS)

Идея поиска в глубину проста: начинаем с некоторой вершины, идем в первого непосещенного соседа, из него - в его непосещенного соседа и так далее, пока не зайдем в тупик. Тогда возвращаемся назад и пробуем другой путь. Такая стратегия называется перебором с возвратами (backtracking).

Это напоминает прохождение лабиринта: вы идете по коридору, всегда сворачивая в первый доступный проход, а когда оказываетесь в тупике - возвращаетесь к последней развилке.

Рекурсивная реализация

Рекурсия - самый естественный способ записать поиск в глубину. Стек вызовов играет роль стека возвратов.

#define MAX_V 100

int adj[MAX_V][MAX_V]; // Матрица смежности
int visited[MAX_V];     // Массив пометок: 0 = не посещена, 1 = посещена
int n;                  // Количество вершин

void DFS(int v) {
    visited[v] = 1;
    printf("%d ", v); // Обработка вершины

    for (int u = 0; u < n; u++) {
        if (adj[v][u] && !visited[u]) {
            DFS(u); // Рекурсивно идем в непосещенного соседа
        }
    }
}

Итеративная реализация (со стеком)

Вместо рекурсии мы вручную управляем стеком - кладем в него вершины, которые нужно обработать:

void DFS_Iterative(int start) {
    int stack[MAX_V];
    int top = -1;

    stack[++top] = start;

    while (top >= 0) {
        int v = stack[top--]; // pop

        if (visited[v]) continue;
        visited[v] = 1;
        printf("%d ", v);

        // Кладем всех непосещенных соседей в стек
        // (в обратном порядке, чтобы порядок обхода совпал с рекурсией)
        for (int u = n - 1; u >= 0; u--) {
            if (adj[v][u] && !visited[u]) {
                stack[++top] = u;
            }
        }
    }
}

Поиск в ширину (Breadth-First Search, BFS)

Поиск в ширину действует иначе: он обходит вершины по уровням. Сначала - все вершины на расстоянии 1 от стартовой, затем на расстоянии 2, потом 3 и так далее. Для этого используется очередь.

Представьте, что вы бросили камень в воду: волна расходится кругами. Поиск в ширину "расходится" от стартовой вершины точно так же, уровень за уровнем.

void BFS(int start) {
    int queue[MAX_V];
    int front = 0, rear = 0;

    queue[rear++] = start;
    visited[start] = 1;

    while (front < rear) {
        int v = queue[front++]; // dequeue
        printf("%d ", v);

        for (int u = 0; u < n; u++) {
            if (adj[v][u] && !visited[u]) {
                visited[u] = 1;
                queue[rear++] = u; // enqueue
            }
        }
    }
}

Сравнение двух обходов

• Структура данных: поиск в глубину использует стек (явный или стек рекурсии), поиск в ширину - очередь.
• Порядок обхода: в глубину - вглубь по одной ветви, в ширину - по уровням.
• Сложность: оба работают за O(N + M) (для списка смежности) или O(N²) (для матрицы смежности).
• Кратчайший путь: поиск в ширину находит кратчайший путь в невзвешенном графе, поиск в глубину - нет.
• Память: поиск в ширину может потребовать O(N) памяти на очередь (если весь уровень широкий). Поиск в глубину расходует O(N) на стек (если граф - длинная цепочка).

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

Оба алгоритма позволяют найти все компоненты связности графа. Идея: запускаем поиск в глубину (или в ширину) из первой непосещенной вершины - она обойдет всю компоненту. Затем ищем следующую непосещенную вершину и запускаем обход снова.

int component[MAX_V]; // component[v] - номер компоненты вершины v
int numComponents = 0;

void FindComponents() {
    for (int v = 0; v < n; v++) visited[v] = 0;

    for (int v = 0; v < n; v++) {
        if (!visited[v]) {
            numComponents++;
            // DFS пометит все вершины этой компоненты
            DFS_MarkComponent(v, numComponents);
        }
    }
}

void DFS_MarkComponent(int v, int comp) {
    visited[v] = 1;
    component[v] = comp;
    for (int u = 0; u < n; u++) {
        if (adj[v][u] && !visited[u]) {
            DFS_MarkComponent(u, comp);
        }
    }
}