Графы и BFS: путь с минимальным числом переходов

Есть станции метро и переходы между ними. Нужно найти маршрут с минимальным числом переходов. Номер станции не говорит о соседстве; список связей описывает отдельную структуру — граф.

Выбираем представление

Вершины — станции, рёбра — допустимые переходы. В ориентированном графе связь u→v не подразумевает обратную. Для двустороннего перехода в списке смежности добавляем оба направления. Петля возвращает вершину к себе; параллельные рёбра связывают ту же пару несколько раз. Решение должно явно сказать, допустимы ли они.

g := [][]int{
    {1, 2}, // из 0
    {3},    // из 1
    {3},    // из 2
    {},     // из 3
    {},     // изолированная 4
}

Список смежности занимает O(V+E) памяти: V вершин, E записей о рёбрах. Матрица смежности имеет V² ячеек и позволяет за O(1) проверить наличие заданного ребра, но просмотр всех соседей вершины требует O(V). Ни одна структура не «лучше вообще»: учитывайте плотность и нужные операции.

Обход слоями

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

parent := make([]int, len(g))
for i := range parent { parent[i] = -1 }
parent[source] = source
queue := []int{source}
for head := 0; head < len(queue); head++ {
    v := queue[head]
    for _, next := range g[v] {
        if parent[next] == -1 {
            parent[next] = v
            queue = append(queue, next)
        }
    }
}

Здесь parent одновременно хранит признак открытия и предшественника. −1 означает «ещё не открыта», а source ссылается на себя. Нужны допустимые source и номера соседей; reference.BFSPath проверяет их до обхода. Сам по себе тип int не доказывает, что индекс существует.

Восстанавливаем маршрут

Если parent[target] остаётся−1, пути нет. Иначе идём от target к parent до source, записываем вершины, затем переворачиваем результат. Для source=target ответ состоит из одной вершины; количество рёбер пути равно len(path)−1.

Для графа из примера есть пути 0→1→3 и 0→2→3. BFS вернёт один из них в зависимости от порядка соседей. Нельзя требовать всегда один и тот же маршрут, если договор обещает только минимальную длину. Детерминированный порядок можно задать отдельно.

Почему путь кратчайший

Очередь извлекает вершины в порядке неубывающего расстояния по числу рёбер. Когда вершина открыта впервые из слоя d, её расстояние d+1. Более короткий путь пришёл бы из более раннего слоя и открыл её раньше. Это доказательство зависит от одинаковой цены каждого перехода.

Если один переход стоит 1 минуту, другой 100, число рёбер не означает минимальное время. Взвешенные пути потребуют другого алгоритма. Время BFS O(V+E), дополнительная память O(V), не считая хранения входного графа.

Практика

Реализуйте BFSPath и проверку входа. Для target3 получите путь длины 2 ребра; для target4 — отсутствие; для source=target — путь из одного элемента. Добавьте цикл, петлю и повторное ребро: обход не должен бесконечно увеличивать очередь.

Для проверки пути проверяйте его начало, конец и существование каждого ребра, затем длину. Не сравнивайте только с одной заранее выбранной последовательностью при нескольких равных вариантах. Практика — 55 минут.

Критерии готовности: каждая вершина ставится в очередь не больше одного раза; направление рёбер соблюдается; отсутствие пути отделено от ошибки входа; результат отвечает выбранной метрике.

Разбор

В этом ориентированном графе путь 0→3 есть, а 3→0 нет. Добавление обратного пути без изменения входа нарушает договор. Изолированная вершина тоже принадлежит графу и должна присутствовать в представлении, даже если у неё пустой список соседей.

Источники: Princeton: undirected graphs и BFS, directed graphs.