Графы и поиск кратчайшего пути

Что такое граф

Граф — это математическая модель, состоящая из вершин и соединяющих их рёбер. Графами описывают дороги между городами, связи в социальных сетях, схемы метро, расписания и многое другое. В одиннадцатом классе графы изучают как способ моделирования и как основу для алгоритмов поиска пути, которые встречаются и в экзаменационных задачах.

Если ребро имеет направление, граф называют ориентированным. Если каждому ребру приписан вес (расстояние, стоимость, время), граф называют взвешенным. Степень вершины — это число выходящих из неё рёбер.

Способы хранения графа

Граф в программе хранят двумя основными способами, и каждый удобен для своих задач.

• Матрица смежности — квадратная таблица, где на пересечении строки и столбца стоит вес ребра или ноль, если связи нет. Удобна, когда рёбер много.
• Список смежности — для каждой вершины перечислены её соседи. Экономит память, когда рёбер немного.

Ниже взвешенный граф задан перечислением рёбер с их весами.

Обходы графа

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

Поиск кратчайшего пути

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

Старт А, расстояния: А=0, остальные = бесконечность Из А: Б=5, В=2 Берём В (минимум): через В путь до Б = 2+1 = 3 < 5, обновляем Б=3 Берём Б: до Г = 3+4 = 7 Итог: кратчайший путь А -> В -> Б -> Г длиной 7

Без алгоритма легко ошибиться: прямой путь А -> Б -> Г равен 5+4=9, а обход через вершину В оказывается короче и равен 7. Алгоритм перебирает варианты системно и гарантированно находит самый дешёвый маршрут.

Связные графы и деревья

Граф называют связным, если из любой вершины можно добраться до любой другой по рёбрам. Особый вид связного графа без циклов — дерево: в нём между двумя вершинами существует ровно один путь. Деревья описывают иерархии: файловую систему, генеалогию, структуру организации. У дерева из n вершин всегда ровно n-1 рёбер, и добавление ещё одного ребра обязательно образует цикл.

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

Обход в глубину: рабочий DFS

DFS отмечает вершину при входе и полностью исследует одну ветвь, прежде чем вернуться к следующему соседу. Порядок зависит от порядка соседей. Он позволяет найти достижимые вершины и путь, но не гарантирует кратчайший путь.

graph = [[1, 2], [0, 3], [0], [1], []]
seen = [False] * len(graph)
parent = [None] * len(graph)
order = []

def dfs(v):
    seen[v] = True
    order.append(v)
    for u in graph[v]:
        if not seen[u]:
            parent[u] = v
            dfs(u)

dfs(0)
print(order)   # [0, 1, 3, 2]
print(parent)  # [None, 0, 0, 1, None]

Вершина 4 из старта 0 недостижима. Путь к 3 восстанавливается по предкам: 3 → 1 → 0, после разворота 0 → 1 → 3. Флаг seen ставят до перехода к соседям, иначе ребро 0—1 могло бы вызвать бесконечное возвращение между двумя вершинами.

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

Для неориентированного графа запустите DFS из каждой ещё не отмеченной вершины; каждый такой запуск начинает новую компоненту. В примере компонентов две: {0,1,2,3} и {4}. Перед отдельным повторным экспериментом заново создайте seen, иначе прежние пометки повлияют на результат.

При списках смежности один полный обход требует O(n + m) операций для n вершин и m рёбер. Глубина рекурсии может достигать n. Для очень длинной цепочки используют явный стек; увеличение лимита рекурсии без оценки памяти не является универсальным решением.

Обход неориентированного графа и достижимость в ориентированном — разные задачи. В ориентированном графе простой подсчёт запусков такого обхода не вычисляет число сильных компонент: для них нужен отдельный алгоритм.

Справочные материалы: Что такое граф — исходная тема. Связанные уроки: Трассировка алгоритма по шагам, Алгоритмы и их эффективность.

Кратко о главном

• Граф — это вершины и рёбра; бывает ориентированным и взвешенным.
• Хранят графы матрицей или списком смежности.
• Обход в ширину использует очередь, в глубину — стек или рекурсию.
• Алгоритм Дейкстры находит кратчайшие пути при неотрицательных весах.
• Посещённые вершины помечают, чтобы не зациклиться.