Задача о минимальном числе рёбер

Мы разобрали, как представить граф: вершины, рёбра, список смежности, матрица. Теперь займёмся обходом. Первый вопрос, который возникает на графе, — а как вообще узнать, что находится в другой его части? Начать с одной вершины, перейти к соседям, от них — к их соседям, и так исследовать достижимую часть графа. Но не просто «пройтись по всем», а найти кратчайший путь. Допустим, у нас есть карта переходов между станциями, и мы хотим от станции s добраться до станции t, сделав как можно меньше пересадок. Каждое ребро графа — это одна пересадка. Значит, нужен путь с минимальным числом рёбер.

Договоримся о контракте. Работаем с невзвешенным графом, где каждое ребро одинаково «дорого»: одна пересадка, один шаг. Если граф взвешенный, но все веса одинаковы и неотрицательны, то же самое рассуждение работает. Но если веса разные — скажем, у дорог разная длина, — BFS напрямую не подходит: он минимизирует число рёбер, а не суммарный вес. Это отдельная задача, и её мы разберём позже. Сейчас — минимум рёбер.

Идея обхода в ширину, или BFS (breadth-first search), проста: мы исследуем граф «слоями». Первый слой — сама начальная вершина s, расстояние 0. Второй слой — все её соседи, расстояние 1. Третий слой — соседи соседей, ещё не посещённые, расстояние 2. И так далее. Каждая вершина попадает в свой слой в зависимости от того, сколько рёбер отделяет её от s. Именно эта послойность и обеспечивает минимальность: если вершина впервые появилась на слое k, то путь до неё состоит из k рёбер, и короче быть не может — все меньшие слои уже просмотрены.

Для реализации нужна очередь — та самая FIFO-структура, которую мы разбирали в 2.5. Вершины обрабатываются в порядке их появления: сначала все на расстоянии 0, потом все на расстоянии 1, и так далее. Очередь здесь — не украшение, а носитель идеи слоёв: именно порядок FIFO обеспечивает, что вершины одного слоя обрабатываются раньше вершин следующего.

Трасса на конкретном графе

Возьмём граф с ромбом: рёбра (0, 1), (0, 2), (1, 3), (2, 3), (3, 4). Плюс вершина 5 изолирована: у неё нет рёбер. Всего вершин 6, номера 0..5. Рёбра ненаправленные.

Запускаем BFS из вершины 0. Инициализация: dist[0] = 0, parent[0] = −1, все остальные dist = −1 (непосещённые), parent = −1. Ставим 0 в очередь.

Шаг 1. Извлекаем 0. Смотрим её соседей в порядке, как они добавлены в список: 1, 2. Оба непосещённые. Для 1: dist[1] = dist[0] + 1 = 1, parent[1] = 0, помещаем в очередь. Для 2: dist[2] = 1, parent[2] = 0, помещаем. Очередь теперь [1, 2].

Шаг 2. Извлекаем 1. Соседи 1: 0 (уже посещён) и 3. Для 3: dist[3] = dist[1] + 1 = 2, parent[3] = 1, помещаем. Очередь [2, 3].

Шаг 3. Извлекаем 2. Соседи 2: 0 (посещён) и 3. 3 уже посещён, пропускаем. Обратите внимание: parent[3] остаётся равным 1, а не переписывается на 2. Это важный момент: первый найденный путь до 3 был через 1, и он уже зафиксирован. Второй путь через 2 имеет ту же длину, и мы его игнорируем. Очередь [3].

Шаг 4. Извлекаем 3. Соседи: 1 и 2 (посещены), 4 (не посещён). Для 4: dist[4] = dist[3] + 1 = 3, parent[4] = 3, помещаем. Очередь [4].

Шаг 5. Извлекаем 4. Соседи: 3 (посещён). Новых нет. Очередь пуста.

Итог: dist = [0, 1, 1, 2, 3, −1], parent = [−1, 0, 0, 1, 3, −1]. Вершина 5 недостижима, dist[5] = −1. Путь к 4 восстанавливается по parent: parent[4] = 3, parent[3] = 1, parent[1] = 0, parent[0] = −1. Читая в обратном порядке: 0 → 1 → 3 → 4. Длина 3, что совпадает с dist[4].

Альтернативный путь 0 → 2 → 3 → 4 имеет ту же длину. Оба минимальны, и BFS находит один из них — тот, который обнаружился первым при обходе соседей в порядке их добавления. Это нормально: минимальных путей может быть несколько, и алгоритм не обязан выбирать «самый красивый» или «самый левый» в каком-то другом смысле. Достаточно того, что он минимален по длине.

Программа

Соберём BFS в C#. Функция Bfs принимает список смежности и стартовую вершину, возвращает массивы dist и parent. Все списки соседей должны существовать и содержать допустимые номера вершин; граф во время обхода не меняется. Дополнительно — функция RestorePath, которая восстанавливает путь от старта до цели по массиву parent. В неё передаётся именно результат Bfs для того же start, а не произвольный массив связей.

using System;
using System.Collections.Generic;

int V = 6;
var adj = new List<int>[V];
for (int i = 0; i < V; i++) adj[i] = new List<int>();
AddEdge(adj, 0, 1);
AddEdge(adj, 0, 2);
AddEdge(adj, 1, 3);
AddEdge(adj, 2, 3);
AddEdge(adj, 3, 4);

var (dist, parent) = Bfs(adj, 0);
Console.WriteLine(string.Join(" ", dist));

var path4 = RestorePath(parent, 0, 4);
Console.WriteLine(path4.Count == 0 ? "(нет пути)" : string.Join(" ", path4));

var path5 = RestorePath(parent, 0, 5);
Console.WriteLine(path5.Count == 0 ? "(нет пути)" : string.Join(" ", path5));

var path0 = RestorePath(parent, 0, 0);
Console.WriteLine(string.Join(" ", path0));

(int[] Dist, int[] Parent) Bfs(List<int>[] adj, int start)
{
    if (adj == null) throw new ArgumentNullException(nameof(adj));
    int n = adj.Length;
    if (start < 0 || start >= n) throw new ArgumentOutOfRangeException(nameof(start));

    int[] dist = new int[n];
    int[] parent = new int[n];
    for (int i = 0; i < n; i++)
    {
        dist[i] = -1;
        parent[i] = -1;
    }

    var queue = new Queue<int>();
    dist[start] = 0;
    queue.Enqueue(start);

    while (queue.Count > 0)
    {
        int u = queue.Dequeue();
        foreach (int v in adj[u])
        {
            if (dist[v] == -1)
            {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                queue.Enqueue(v);
            }
        }
    }
    return (dist, parent);
}

List<int> RestorePath(int[] parent, int start, int target)
{
    if (parent == null) throw new ArgumentNullException(nameof(parent));
    var result = new List<int>();
    if (target < 0 || target >= parent.Length) throw new ArgumentOutOfRangeException(nameof(target));
    if (start < 0 || start >= parent.Length) throw new ArgumentOutOfRangeException(nameof(start));

    if (start == target)
    {
        result.Add(start);
        return result;
    }
    if (parent[target] == -1) return result;

    int current = target;
    while (current != -1)
    {
        result.Add(current);
        current = parent[current];
    }
    result.Reverse();
    return result;
}

void AddEdge(List<int>[] adj, int u, int v)
{
    if (u < 0 || u >= adj.Length || v < 0 || v >= adj.Length)
        throw new ArgumentException("Конец ребра вне диапазона.");
    adj[u].Add(v);
    adj[v].Add(u);
}

Вывод:

0 1 1 2 3 -1
0 1 3 4
(нет пути)
0

Разберём. Массив dist совпадает с нашей трассой: 0 1 1 2 3 −1. Путь к 4: 0 1 3 4. Путь к 5: недостижим, parent[5] = −1, поэтому RestorePath возвращает пустой список, и мы печатаем «(нет пути)». Путь к 0 из 0: единственная вершина, сам старт, поэтому [0].

Обратите внимание на порядок операций в BFS. Мы помечаем вершину посещённой в тот момент, когда добавляем её в очередь, а не когда извлекаем. Это принципиально: если бы мы помечали при извлечении, одну и ту же вершину можно было бы добавить в очередь несколько раз, пока она ещё не извлечена. Пометка при добавлении гарантирует, что каждая достижимая вершина попадёт в очередь ровно один раз, и это делает обход линейным.

Почему BFS находит кратчайший путь? Ключевое свойство: в очереди вершины хранятся в порядке неубывания dist. Когда мы извлекаем вершину u с dist[u] = k, все следующие вершины в очереди имеют dist не меньше k. Новые соседи получают k + 1 и добавляются в хвост, поэтому порядок слоёв сохраняется. Значит, когда мы впервые обнаруживаем какую-то вершину v, её расстояние устанавливается как dist[u] + 1, где u — её первый найденный предшественник. Если бы существовал более короткий путь к v длины меньше, то предшественник v на этом пути был бы обработан раньше, и v обнаружилась бы с меньшим расстоянием. Противоречие. Значит, первое установленное расстояние минимально.

Это рассуждение важно не путать с фразой «любой обход даёт кратчайший путь». Это неверно: DFS, например, не даёт кратчайшего пути в невзвешенном графе — он уходит вглубь и может найти длинный путь раньше короткого. Именно послойный порядок BFS обеспечивает минимальность, и он держится на FIFO-очереди.

Стоимость BFS: O(V + E) с учётом инициализации массивов. Инициализация dist и parent занимает O(V). Очередь обрабатывает каждую достижимую вершину ровно один раз, потому что мы помечаем при добавлении. Для каждой вершины мы перебираем её соседей. Суммарно по всем вершинам это O(E) для направленного графа и O(2E) = O(E) для ненаправленного: каждое ребро просматривается один раз из каждого конца (или один раз, если граф направленный). Итого O(V + E).

Память: массивы dist и parent по O(V), очередь может содержать до O(V) вершин. Итого O(V) дополнительной памяти. Граф в памяти занимает O(V + E).

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

BFS от одного старта не обходит весь граф, если граф несвязный. В нашем примере вершина 5 осталась недостижимой, и её dist = −1. Чтобы обойти весь граф, нужно запустить BFS из каждой непосещённой вершины: это стандартный приём, и мы его будем использовать, когда речь пойдёт о компонентах связности.

Для направленного графа BFS работает точно так же, но использует только исходящие рёбра: мы перебираем соседей u в списке смежности, а туда попадают только те вершины, куда ведёт ребро из u. Обратные рёбра не учитываются.

Невзвешенный циклический граф не вызывает зацикливания именно благодаря массиву dist: если мы уже посетили вершину, мы её не добавляем в очередь повторно, и цикл в графе не приводит к бесконечному обходу. Это та самая защита, которая отличает обход графа от простого «идти по связям»: без неё мы бы ходили по циклу бесконечно.

И последнее про путь. Мы восстанавливаем его по массиву parent, идя от цели к старту и разворачивая результат. Если цель недостижима, parent[target] = −1, и мы возвращаем пустой список. Если цель совпадает со стартом, путь состоит из одной вершины. Это естественные края, и их стоит обрабатывать явно.

Следующий урок — обход в глубину, или DFS. Он устроен иначе: идёт вглубь, пока может, а потом возвращается и пробует другие ветви. DFS не даёт кратчайших путей, зато естественно подходит для других задач: проверки связности, поиска циклов, топологической сортировки. Об этом — дальше.