Основы графов на Python

Введение в графы и терминология

Зачем нужны графы

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

Примеры задач, которые удобно формулировать как графовые:

социальные сети: люди и дружба

карты и навигация: перекрёстки и дороги

зависимости в проекте: задачи и зависимости

компьютерные сети: устройства и соединения

рекомендации: пользователи, товары и взаимодействия

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

Граф — это математическая модель, состоящая из вершин и рёбер.

Часто граф записывают так: .

Здесь:

— сам граф

— множество вершин (узлов)

— множество рёбер (связей между вершинами)

Если ребро соединяет две вершины и , его можно записать как . Смысл зависит от типа графа:

в неориентированном графе и означают одно и то же ребро

в ориентированном графе означает направление из в

Полезная вводная (и терминология на русском) есть в статье Википедии: Теория графов.

!Пример простого неориентированного графа: вершины и рёбра

Основные виды графов

Ниже — самые распространённые разновидности, которые встретятся в задачах и в Python-представлениях.

| Вид графа | Что это означает | Где встречается | |---|---|---| | Неориентированный | Рёбра без направления | дороги с двусторонним движением, дружба в соцсети | | Ориентированный | У ребра есть направление | подписки, зависимости задач | | Взвешенный | У ребра есть вес (число) | расстояния, цены, задержки | | Невзвешенный | Все рёбра “равны” | связи типа “есть/нет” | | Простой | Нет петель и кратных рёбер | многие учебные задачи | | Мультиграф | Между двумя вершинами могут быть несколько рёбер | несколько рейсов между городами | | С петлями | Ребро может вести из вершины в неё же | состояния автомата, специфичные модели |

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

Базовая терминология

Вершины и рёбра

Вершина (узел) — объект в графе

Ребро — связь между двумя вершинами

Петля — ребро вида , соединяющее вершину саму с собой

Кратные рёбра — несколько рёбер между одной и той же парой вершин

Смежность и инцидентность

вершины смежны, если между ними есть ребро

ребро инцидентно вершине, если оно “касается” этой вершины (входит в неё)

Степень вершины

Степень вершины в неориентированном графе — это количество рёбер, инцидентных этой вершине.

В ориентированном графе обычно различают:

входящую степень (in-degree) — сколько рёбер входит в вершину

исходящую степень (out-degree) — сколько рёбер выходит из вершины

Полезный факт для неориентированных графов:

Объяснение каждого элемента:

— множество всех вершин

— “вершина принадлежит множеству вершин ”

— степень вершины

— сумма степеней по всем вершинам

— множество всех рёбер

— количество рёбер

Почему справа стоит : каждое ребро в неориентированном графе добавляет по 1 к степени двух своих концов.

Маршрут, путь, цикл

Эти понятия описывают “как можно пройти” по графу.

маршрут — последовательность вершин, где каждая следующая соединена ребром с предыдущей

длина маршрута — количество рёбер, пройденных по этому маршруту

путь — маршрут без повторения рёбер (в некоторых определениях — без повторения вершин; важно уточнять в конкретной задаче)

простой путь — путь без повторения вершин

цикл — путь, который начинается и заканчивается в одной и той же вершине

Практический смысл:

поиск кратчайшего пути — навигация и логистика

поиск циклов — анализ зависимостей и обнаружение “замкнутых” проблем

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

Для неориентированного графа:

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

компонента связности — максимальная “связная часть” графа

Для ориентированного графа часто используют два разных понятия:

сильная связность — из любой вершины можно добраться до любой другой, учитывая направления рёбер

слабая связность — если игнорировать направления, то граф становится связным

Часто встречающиеся специальные структуры

дерево — связный неориентированный граф без циклов

лес — набор деревьев (граф без циклов, но не обязательно связный)

DAG (Directed Acyclic Graph) — ориентированный граф без циклов

двудольный граф — вершины можно разделить на две группы так, что рёбра идут только между группами

Эти структуры важны, потому что для них существуют особенно эффективные алгоритмы.

Как представлять граф в Python

В Python нет “встроенного” типа графа, поэтому граф обычно хранят в одном из стандартных представлений.

Список рёбер

Храним граф как список пар вершин.

Плюсы:

просто создать и сериализовать

Минусы:

медленно отвечать на вопрос “кто соседи вершины?”

Список смежности

Для каждой вершины храним список (или множество) её соседей.

Плюсы:

быстро получать соседей

компактно для разреженных графов (когда рёбер мало по сравнению с числом возможных)

Практическая деталь:

если граф неориентированный, ребро ("A", "B") обычно добавляют в обе стороны: A -> B и B -> A

если граф ориентированный, добавляют только по направлению

Документация по словарям Python: Built-in Types — dict.

Матрица смежности

Это таблица , где — число вершин. В ячейке стоит:

1 или True, если ребро есть

0 или False, если ребра нет

Плюсы:

очень быстро проверять “есть ли ребро между и ?”

Минусы:

занимает много памяти на больших графах

!Связь между графом и его матрицей смежности

Взвешенные графы в Python

Если у ребра есть вес (например, расстояние), список смежности часто делают таким:

Интерпретация записи ("B", 5):

сосед — вершина "B"

вес ребра — 5

Что будет дальше в курсе

Эта статья задала основные слова и способы “думать” о графах. Дальше обычно переходят к двум практическим линиям:

обходы и поиск достижимости: BFS и DFS

задачи на пути и структуры: кратчайшие пути, деревья, циклы, компоненты

По мере продвижения мы будем опираться на определения из этой статьи и реализовывать алгоритмы на Python поверх списков смежности и других представлений.

Представление графов в Python

Как эта тема связана с предыдущей

В предыдущей статье мы договорились, что граф — это вершины и рёбра, а также разобрали ориентированные/неориентированные и взвешенные/невзвешенные графы. Теперь сделаем следующий практический шаг: научимся хранить граф в Python так, чтобы удобно было писать алгоритмы (например, обходы BFS/DFS и поиск путей).

В Python нет встроенного типа граф, поэтому мы выбираем структуру данных под нужные операции:

быстро ли нужно находить соседей вершины

часто ли мы проверяем «есть ли ребро между и »

много ли вершин и рёбер (граф плотный или разреженный)

нужны ли веса, направления, кратные рёбра

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

!Один и тот же граф в трёх популярных представлениях

Какие операции нам обычно нужны

Перед выбором представления полезно проговорить типовые операции:

получить всех соседей вершины v

проверить, есть ли ребро u -> v (или u — v)

добавить ребро

пробежать все рёбра графа

Разные представления делают разные операции дешевле.

Список рёбер

Идея

Граф хранится как список пар вершин. Для взвешенного графа — как список троек.

Пример

Когда удобно

когда нужно просто хранить и передавать граф (например, из файла)

когда алгоритм и так проходит по всем рёбрам (например, некоторые задачи на сортировку/фильтрацию рёбер)

Ограничения

чтобы найти соседей вершины, придётся просматривать почти весь список рёбер

проверка «есть ли ребро между u и v» тоже часто требует полного прохода

Список смежности

Идея

Для каждой вершины храним её соседей. В Python это обычно словарь: ключ — вершина, значение — список/множество соседей.

Документация по словарям: Mapping Types — dict.

Невзвешенный граф

Важная деталь про неориентированный граф

Если граф неориентированный и есть ребро A—B, то в списке смежности обычно хранят в обе стороны:

A содержит B

B содержит A

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

Список или множество соседей

Часто удобнее хранить соседей как set:

проще избегать дублей

быстрее проверять, является ли вершина соседом (x in neighbors)

Документация по множествам: Built-in Types — set.

Пример:

Взвешенный граф (список смежности)

Тогда у каждой вершины лежат пары (сосед, вес).

Здесь каждая пара означает:

первый элемент — куда ведёт ребро

второй элемент — вес ребра (например, расстояние или цена)

Ориентированный граф (список смежности)

Для ориентированного графа в adj[u] лежат вершины, в которые есть ребро из u.

Удобное построение через defaultdict

Если вы постоянно добавляете рёбра, удобно использовать defaultdict.

Документация: collections — defaultdict.

Матрица смежности

Идея

Это таблица , где — число вершин. Ячейка отвечает на вопрос «есть ли ребро между вершинами с индексами i и j».

Чтобы построить матрицу, обычно нужно:

собрать список вершин

сопоставить каждой вершине индекс 0..n-1

создать матрицу и заполнять её

Пример для невзвешенного графа

Взвешенная матрица

Для весов часто используют:

0 или None — если ребра нет

число — если ребро есть и это его вес

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

Когда матрица выгодна

когда граф плотный (рёбер много)

когда очень часто нужно отвечать на вопрос «есть ли ребро между u и v»

Минус

Память растёт как . Это означает: если вершин много, матрица может стать слишком большой даже при малом числе рёбер.

Сравнение представлений

| Представление | Память | Соседи вершины | Проверка ребра u-v | Комментарий | |---|---|---|---|---| | Список рёбер | обычно компактно | медленно (нужен проход) | медленно (нужен проход) | хорош для хранения/ввода/вывода | | Список смежности | хорошо для разреженных | быстро | зависит от типа контейнера | универсальный выбор для алгоритмов | | Матрица смежности | дорого на больших | можно получить, но нужен проход по строке | очень быстро | хороша для плотных графов |

Практические рекомендации для курса

В этом курсе дальше чаще всего будет использоваться список смежности (словарь), потому что он:

естественно отражает понятие «соседи вершины»

удобен для BFS/DFS и поиска компонент связности

легко расширяется до взвешенных и ориентированных графов

Когда понадобится матрица смежности:

в задачах, где критична быстрая проверка существования ребра

когда вершин мало, а плотность графа высокая

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

Мини-шаблоны: как договориться о формате графа в коде

Чтобы код с графами был читаемым, полезно фиксировать соглашения:

какие типы у вершин: строки, числа, объекты

ориентированный граф или нет

где хранятся веса (если есть)

допускаются ли кратные рёбра и петли

Один из простых вариантов соглашения для курса:

невзвешенный граф: dict[str, list[str]] или dict[str, set[str]]

взвешенный граф: dict[str, list[tuple[str, int]]] (или float для весов)

Этого достаточно, чтобы дальше уверенно писать обходы, искать пути и анализировать структуру графа.

Обход графов: BFS и DFS

Как эта тема связана с предыдущими

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

Обход графа нужен, чтобы:

понять, какие вершины достижимы из заданной

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

восстановить путь

проверить наличие циклов (обычно через DFS)

найти кратчайшие расстояния в невзвешенном графе (через BFS)

В этой статье мы разберём два базовых обхода:

BFS (breadth-first search, поиск в ширину)

DFS (depth-first search, поиск в глубину)

Дальше по курсу эти обходы будут использоваться как “двигатель” для более сложных задач.

Предварительные соглашения

Чтобы код был понятным и единым по курсу, будем использовать список смежности.

Невзвешенный граф будем хранить так:

Общая идея обхода:

мы выбираем стартовую вершину start

используем структуру данных, чтобы решать какую вершину обрабатывать следующей

поддерживаем множество visited, чтобы не ходить по кругу бесконечно

> В графах часто есть циклы, поэтому visited почти всегда обязателен.

!Наглядное сравнение порядка посещения вершин при BFS и DFS

BFS

Интуиция

BFS идёт “слоями” от стартовой вершины:

сначала посещает всех соседей start

затем соседей соседей

затем следующий слой, и так далее

Из-за этого BFS в невзвешенном графе даёт ключевое свойство:

если считать каждое ребро за “стоимость 1”, то BFS находит кратчайшее число рёбер от start до любой достижимой вершины

Какая структура данных нужна

BFS использует очередь (FIFO: первым вошёл, первым вышел).

В Python для очереди обычно берут collections.deque, потому что pop(0) у списка работает медленно на больших данных.

Ссылка: collections.deque.

BFS: достижимость

Задача: обойти все вершины, достижимые из start.

Комментарии к ключевым строкам:

visited = set([start]) означает, что стартовую вершину мы считаем “увиденной” сразу, чтобы не добавить её в очередь повторно через соседей

q.popleft() достаёт вершину из начала очереди

adj.get(v, []) безопасно обрабатывает случай, когда у вершины нет записи в словаре

BFS: кратчайшие расстояния и восстановление пути

Чтобы получить кратчайшие расстояния (в рёбрах) и восстановить маршрут до конкретной вершины, обычно хранят:

dist[v] расстояние от start до v

parent[v] предка, из которого мы пришли в v впервые

Как это использовать:

Почему путь получится кратчайшим:

BFS обрабатывает вершины по слоям

первая встреча вершины to происходит через минимальное число рёбер

поэтому parent фиксирует переходы, соответствующие кратчайшим путям

DFS

Интуиция

DFS старается уйти “как можно глубже” по одному пути:

идём в первого соседа

из него идём в его соседа

и так далее, пока упираемся

затем возвращаемся назад и пробуем другие варианты

DFS особенно полезен как основа для задач про:

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

поиск циклов

топологическую сортировку в DAG (позже в курсе)

Два способа реализации

DFS можно реализовать:

рекурсивно (обычно короче)

итеративно (через явный стек)

Рекурсивный вариант в Python может упереться в ограничение глубины рекурсии на больших графах. Ссылка: sys.setrecursionlimit.

DFS: рекурсивный вариант

Здесь порядок order зависит от порядка соседей в adj[v].

DFS: итеративный вариант (через стек)

Стек работает по принципу LIFO: последним положили, первым достали.

Практическая деталь:

в итеративном DFS вершина может попасть в stack несколько раз (из разных соседей)

поэтому удобно проверять visited в момент извлечения

Важное: ориентированный и неориентированный граф

Алгоритмы BFS/DFS одинаковы, меняется только смысл списка смежности.

в ориентированном графе adj[u] содержит вершины, в которые есть ребро из u

в неориентированном графе ребро u—v обычно записывают в обе стороны, иначе обход увидит только половину связей

Что именно возвращает обход

BFS и DFS часто используют не ради “порядка”, а ради информации, которую можно собрать по пути.

Типичные результаты:

visited как ответ на вопрос “какие вершины достижимы?”

parent для восстановления пути

dist для кратчайших расстояний в невзвешенном графе (BFS)

Сложность по времени и памяти

Если граф хранится списком смежности, то и BFS, и DFS работают за время порядка .

Расшифровка обозначений:

это множество вершин графа

это количество вершин

это множество рёбер графа

это количество рёбер

запись означает, что время растёт примерно пропорционально числу вершин плюс числу рёбер, потому что:

- каждую вершину мы помечаем посещённой не более одного раза - каждое ребро (точнее, каждая запись в списке смежности) мы просматриваем в цикле по соседям

По памяти:

visited занимает место примерно пропорционально числу посещённых вершин

BFS хранит очередь, DFS хранит стек (в худшем случае туда может попасть много вершин)

Частые ошибки и как их избежать

Забыли visited: на графе с циклом обход может стать бесконечным.

Перепутали ориентацию: если граф ориентированный, не нужно добавлять ребро “в обе стороны”.

Использовали список как очередь: pop(0) на больших данных станет узким местом, берите deque.

Рекурсивный DFS на очень глубоком графе: возможна ошибка глубины рекурсии, используйте итеративный DFS.

Что дальше

В следующих темах BFS и DFS будут применяться как базовый инструмент:

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

поиск циклов

построение дерева обхода

задачи на пути (в том числе кратчайшие)

Важно, чтобы вы уверенно реализовывали оба обхода на списке смежности и понимали, какую структуру данных (очередь или стек) требует каждый алгоритм.

Поиск кратчайших путей: Дейкстра и Беллман—Форд

Как эта тема связана с предыдущими

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

расстояние (км)

время (мин)

цена

задержка

Тогда «кратчайший» путь — это уже не «с наименьшим числом рёбер», а «с минимальной суммой весов». Для этого нужны алгоритмы для взвешенных графов.

В этой статье разберём два базовых алгоритма:

Дейкстра — быстрый и популярный, но требует неотрицательные веса

Беллман—Форд — медленнее, зато умеет работать с отрицательными весами и обнаруживает отрицательные циклы

Постановка задачи: что такое кратчайший путь во взвешенном графе

Пусть есть путь из вершины start в вершину t:

start -> ... -> t

Если веса рёбер на этом пути равны , то стоимость пути (его «длина») равна:

Объяснение элементов формулы:

— суммарная стоимость пути

— знак суммы («сложить все»)

— номер ребра в пути

— количество рёбер в пути

— вес -го ребра

Задача кратчайшего пути: найти путь с минимальным .

Соглашение о представлении графа в Python

Как и в предыдущих статьях, будем использовать список смежности, но для взвешенного графа:

Граф может быть ориентированным или неориентированным:

для ориентированного добавляем только u -> v

для неориентированного обычно добавляют оба направления: u -> v и v -> u с одним и тем же весом

!Пример взвешенного графа и выделенный кратчайший путь

Алгоритм Дейкстры

Когда применять

Алгоритм Дейкстры применим, если:

все веса рёбер неотрицательные (то есть для каждого ребра)

Он часто используется для:

навигации и логистики

кратчайших путей в сетях

задач «минимальной стоимости» без штрафов со знаком минус

Если в графе есть отрицательное ребро, Дейкстра может выдать неверный ответ.

Интуиция

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

Ключевой смысл неотрицательных весов:

если мы уже нашли самый дешёвый способ добраться до вершины v, то «дешевле позже» уже не получится, потому что любые дополнительные рёбра только увеличивают стоимость (или оставляют как есть при нулевом весе)

Что такое релаксация

Для ребра u -> v веса w делаем проверку:

если dist[u] + w < dist[v], то мы нашли более короткий путь в v, и нужно обновить dist[v] и запомнить предка parent[v] = u

Это обновление обычно называют релаксацией.

Реализация на Python через heapq

Дейкстра требует структуру «достать вершину с минимальным расстоянием», поэтому удобно использовать кучу (min-heap).

Документация: heapq — Heap queue algorithm.

Почему появляются «устаревшие» записи:

мы не умеем «уменьшать ключ» прямо внутри heapq

вместо этого мы добавляем новую пару (new_dist, вершина)

старая запись остаётся в куче, и при извлечении мы её игнорируем

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

parent хранит предка на кратчайшем пути. Восстановление такое же по идее, как мы делали для BFS.

Сложность

При списке смежности и куче Дейкстра обычно работает быстро на больших разреженных графах. В учебной практике достаточно помнить:

он заметно быстрее Беллмана—Форда

но требует неотрицательных весов

Дополнительное чтение: Dijkstra's algorithm.

Алгоритм Беллмана—Форда

Когда применять

Беллман—Форд применяют, если:

в графе могут быть отрицательные веса

нужно обнаружить отрицательный цикл, который делает задачу «кратчайшего пути» некорректной

Пример смысла отрицательного ребра:

«скидка», «кэшбэк», «прибыль» со знаком минус в модели стоимости

Что такое отрицательный цикл и почему это проблема

Цикл — это маршрут, который возвращается в исходную вершину.

Если сумма весов по циклу отрицательна, то это отрицательный цикл. Тогда можно:

пройти цикл один раз и уменьшить стоимость пути

пройти цикл два раза и уменьшить ещё сильнее

и так бесконечно

То есть «самого короткого пути» не существует: стоимость может уходить к .

Интуиция

Беллман—Форд многократно делает релаксации всех рёбер.

Факт, на который он опирается:

если нет отрицательных циклов, то кратчайший путь до любой вершины содержит не более рёбер

Объяснение элементов:

— множество вершин

— количество вершин

— «на одну меньше числа вершин»

Почему так: если в пути было бы рёбер, то по принципу Дирихле какая-то вершина повторилась бы, значит есть цикл; цикл можно выбросить (если он не отрицательный), и путь не станет хуже.

Отсюда алгоритм:

повторить релаксацию всех рёбер раз

затем сделать ещё одну «контрольную» итерацию: если хоть что-то улучшается, значит есть отрицательный цикл, достижимый из start

Реализация на Python

Удобно сначала получить список всех рёбер.

Что означает результат:

если третий результат True, то найден отрицательный цикл (и обычные кратчайшие пути не определены)

иначе dist и parent корректны, и путь можно восстанавливать функцией restore_path

Дополнительное чтение: Bellman–Ford algorithm.

Сложность

Беллман—Форд обычно заметно медленнее Дейкстры, потому что многократно проходит по всем рёбрам. Его стоит выбирать, когда это действительно нужно из-за отрицательных весов или требования обнаружить отрицательный цикл.

Как выбрать алгоритм

| Ситуация | Что выбрать | Почему | |---|---|---| | Веса неотрицательные | Дейкстра | быстрее и стандартен | | Есть отрицательные веса | Беллман—Форд | Дейкстра может ошибаться | | Нужно обнаружить отрицательный цикл | Беллман—Форд | имеет встроенную проверку | | Невзвешенный граф (все веса = 1) | BFS | проще и быстрее в этой частной задаче |

Мини-пример: сравнение на одном графе

Граф без отрицательных весов

Здесь кратчайший путь A -> C -> B -> D имеет стоимость .

Граф с отрицательным весом (без отрицательного цикла)

Если попытаться применить Дейкстру к такому графу, она не обязана работать правильно.

Частые ошибки

Запустили Дейкстру на графе с отрицательными весами: ответ может быть неверным.

Забыли про “устаревшие” элементы в куче в реализации Дейкстры на heapq: получите лишнюю работу или ошибки логики.

Неверно храните неориентированный граф: если ребро u—v, но вы добавили только u -> v, алгоритм будет считать граф ориентированным.

Интерпретируете “нет пути” как 0: обычно «нет пути» — это inf (в коде float("inf")).

Что дальше

Теперь у вас есть полный базовый набор для путей:

BFS для невзвешенных графов

Дейкстра для взвешенных графов без отрицательных весов

Беллман—Форд для отрицательных весов и поиска отрицательных циклов

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

Остовные деревья: Краскал и Прим

Как эта тема связана с предыдущими

Ранее мы научились:

представлять граф в Python (список смежности и другие формы)

обходить граф (BFS и DFS)

искать кратчайшие пути (Дейкстра и Беллман—Форд)

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

Это полезно, когда нужно соединить все объекты с минимальной суммарной стоимостью:

прокладка кабелей между зданиями

проектирование сети дорог/труб

построение дешёвой связной инфраструктуры

Что такое остовное дерево

Пусть дан неориентированный граф .

Остов означает, что мы берём все вершины из .

Дерево означает, что подграф:

- связный - без циклов

Остовное дерево графа — это подграф, который:

содержит все вершины исходного графа

является деревом

Практический факт (без формул): если в графе вершин, то в любом дереве на этих вершинах будет ровно ребро. Это удобно для проверок.

Минимальное остовное дерево (MST)

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

Суммарный вес дерева можно записать формулой:

Расшифровка:

— множество рёбер выбранного остовного дерева

— ребро принадлежит дереву

— вес (стоимость) ребра

— операция суммы «сложить все веса рёбер дерева»

— итоговая суммарная стоимость

Минимальное остовное дерево (Minimum Spanning Tree, MST) — это остовное дерево с минимальным возможным .

Важные условия и уточнения:

классическая постановка MST: неориентированный граф

если граф несвязный, то остовного дерева для всех вершин не существует; вместо этого строят минимальный остовный лес (по MST на каждую компоненту связности)

MST может быть не единственным, если есть равные веса

Дополнительное чтение: Minimum spanning tree.

!Пример: исходный взвешенный граф и выделенное минимальное остовное дерево

Два основных алгоритма: Краскал и Прим

Оба алгоритма решают одну и ту же задачу MST, но делают это по-разному:

Краскал: сортируем рёбра по весу и добавляем самые дешёвые, избегая циклов

Прим: растим одно дерево от стартовой вершины, каждый раз добавляя самое дешёвое ребро, которое ведёт наружу

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

Алгоритм Краскала

Идея

Отсортировать все рёбра по возрастанию веса.

Идти по рёбрам от самых дешёвых к самым дорогим.

Добавлять ребро, только если оно не создаёт цикл.

Остановиться, когда набрали ребро (для связного графа).

Ключевой вопрос: как быстро проверять «создаст ли ребро цикл»?

Для этого используют структуру DSU (Disjoint Set Union, она же Union-Find): она поддерживает разбиение вершин на компоненты и умеет быстро отвечать, в одной ли компоненте две вершины.

Дополнительное чтение:

Kruskal's algorithm

Disjoint-set data structure

Представление графа

Краскалу удобнее всего подавать граф как список рёбер:

невзвешенный: (u, v)

взвешенный: (u, v, w)

При этом граф неориентированный: ребро u—v хранится один раз.

Реализация DSU на Python

Реализация Краскала

Практические замечания:

если граф несвязный, то Краскал вернёт лес (меньше чем ребро)

чтобы корректно использовать условие остановки, удобно заранее привести vertices к списку (иначе list(vertices) внутри цикла может быть ошибкой для итераторов)

Более аккуратный вариант с предобработкой:

Алгоритм Прима

Идея

Прим строит MST как «растущее дерево»:

Выбираем стартовую вершину start.

Держим множество in_mst: какие вершины уже в дереве.

Смотрим на все рёбра, которые выходят из дерева наружу.

Каждый раз выбираем самое дешёвое такое ребро и добавляем его.

Это похоже по духу на Дейкстру из предыдущей статьи:

там мы выбирали вершину с минимальной текущей дистанцией

здесь выбираем ребро с минимальным весом, которое расширяет построенную часть

Дополнительное чтение: Prim's algorithm.

Представление графа

Приму удобно работать со списком смежности взвешенного графа:

Для неориентированного графа каждое ребро записывают в обе стороны.

Реализация Прима через heapq

Мы будем хранить в куче кандидаты-рёбра вида (w, u, v):

w — вес

u — вершина внутри уже построенного дерева

v — вершина, которую хотим присоединить

Документация по куче: heapq — Heap queue algorithm.

Практические замечания:

если граф связный и start лежит в нём, Прим построит MST и добавит ребро

если граф несвязный, Прим построит MST только для компоненты связности вершины start

Чтобы получить минимальный остовный лес для несвязного графа, можно запускать Прим из каждой непосещённой вершины и объединять результаты.

Как выбрать между Краскалом и Примом

| Критерий | Краскал | Прим | |---|---|---| | Основная идея | выбирать рёбра по возрастанию веса, избегая циклов | растить дерево от старта, всегда брать лучшее выходящее ребро | | Удобное представление | список рёбер | список смежности | | Нужная структура | DSU (Union-Find) | куча (heapq) | | Несвязный граф | естественно даёт лес | даёт дерево только для компоненты старта | | Когда часто удобнее | когда рёбра уже есть списком и их легко сортировать | когда граф уже хранится как adj и хочется «от старта» |

Проверки корректности результата

Если вы получили набор рёбер mst_edges, полезно проверить базовые свойства:

в связном графе количество рёбер должно быть

структура не должна содержать циклов

все вершины должны быть достижимы (для связного графа)

Для учебной проверки достижимости можно применить BFS/DFS из предыдущей статьи по графу, построенному только из рёбер MST.

Частые ошибки

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

Хранят неориентированное ребро только в одну сторону в adj: Прим тогда работает на «сломанных» данных.

В Краскале не используют DSU и пытаются проверять циклы обходом на каждое ребро: это сильно замедляет алгоритм.

В Приме забывают проверку if v in in_mst: тогда можно добавить вершину повторно и испортить результат.

Что дальше по курсу

Алгоритмы MST часто идут рядом с темами про пути, потому что это ещё один фундаментальный класс задач на взвешенных графах.

Дальше естественно решать прикладные задачи:

построение дешёвой сети и анализ выигрыша по стоимости

сравнение MST и кратчайших путей (это разные задачи: MST не гарантирует кратчайшие пути между парами вершин)

минимальный остовный лес для несвязных графов

Если позже захотите использовать готовую реализацию, можно посмотреть на функции MST в NetworkX, но для понимания алгоритмов очень полезно один раз реализовать Краскала и Прима самостоятельно.

Топологическая сортировка и DAG-задачи

Как эта тема связана с предыдущими

Ранее мы научились представлять графы в Python и делать обходы BFS/DFS. Топологическая сортировка напрямую опирается на эти идеи:

мы всё так же работаем со списком смежности

нам снова нужны понятия достижимость и циклы

DFS даёт один из стандартных способов построить топологический порядок

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

DAG: ориентированный ациклический граф

DAG (Directed Acyclic Graph) — это ориентированный граф без циклов.

ориентированный означает, что ребро имеет направление

ациклический означает, что нельзя стартовать из вершины и по направлениям рёбер вернуться в неё же

DAG — естественная модель для зависимостей: если задача должна быть выполнена раньше задачи , удобно записать ребро .

Полезная справка: Directed acyclic graph — Wikipedia.

!Пример DAG и один из возможных топологических порядков

Что такое топологическая сортировка

Топологическая сортировка — это упорядочивание вершин ориентированного графа так, что для каждого ребра вершина стоит раньше .

Ключевой факт:

топологическая сортировка существует только для DAG

если в графе есть ориентированный цикл, корректный порядок невозможен

Справка: Topological sorting — Wikipedia.

Представление графа для задач на топологию

Будем использовать список смежности для ориентированного графа:

Практическая деталь: вершины, у которых нет исходящих рёбер, всё равно полезно хранить в словаре с пустым списком, чтобы они не “потерялись” при обходах.

Алгоритм Кана

Идея

Алгоритм Кана строит порядок, постоянно выбирая вершины с нулевой входящей степенью.

Определение: входящая степень вершины — это число рёбер вида .

Шаги алгоритма:

Посчитать indegree[v] для всех вершин.

Положить в очередь все вершины с indegree == 0.

Пока очередь не пуста:

- достать вершину v, добавить её в ответ - для каждого соседа to уменьшить indegree[to] на 1 - если indegree[to] стал равен 0, добавить to в очередь

Почему это работает:

вершина с indegree == 0 не зависит ни от чего “слева”, значит её можно ставить следующей

удаляя такую вершину, мы “снимаем” зависимость с её потомков

Реализация на Python

Как интерпретировать результат:

функция вернула список — это корректный топологический порядок

функция вернула None — в графе есть ориентированный цикл

Сложность

При списке смежности алгоритм работает за время порядка , потому что:

каждую вершину мы помещаем в очередь и извлекаем не более одного раза

каждое ребро мы рассматриваем ровно один раз, когда уменьшаем indegree

Здесь:

— число вершин

— число рёбер

Топологическая сортировка через DFS

Идея

DFS можно использовать так:

запускаем DFS из всех непосещённых вершин

добавляем вершину в ответ после обработки всех её исходящих рёбер

в конце переворачиваем список

Интуиция: вершина должна оказаться раньше тех, в кого она ведёт, поэтому она попадает в ответ “позже” и затем разворачивается.

Детектирование циклов через цвета

Для ориентированного графа удобно хранить состояние вершины:

0 — не посещена

1 — в процессе обхода (на текущем стеке рекурсии)

2 — полностью обработана

Если из вершины в состоянии 1 мы попадаем в вершину 1, найдено ребро “назад”, значит есть цикл.

Реализация

Практическое замечание: этот вариант использует рекурсию, поэтому на очень глубоких графах может потребоваться итеративная версия DFS.

Что выбрать: Кан или DFS

| Критерий | Алгоритм Кана | DFS-подход | |---|---|---| | Основная структура | очередь вершин с indegree == 0 | рекурсия или стек | | Проверка на цикл | если обработано меньше вершин, чем всего | через “цвета” (состояния) | | Когда часто удобнее | зависимости и “снятие блокировок” | когда DFS уже используется в коде |

На практике оба варианта одинаково полезны, важно уверенно владеть хотя бы одним.

Типовые DAG-задачи

Проверка корректности зависимостей

Задача: есть зависимости задач, нужно понять, можно ли выполнить всё без “замкнутых” требований.

Решение:

строим ориентированный граф зависимостей

запускаем топологическую сортировку

если ответа нет, значит есть цикл зависимостей

Построение порядка выполнения работ

Задача: вывести один из допустимых порядков (сборка проекта, запуск пайплайна).

Решение:

топологическая сортировка возвращает допустимый порядок

если возможных порядков много, алгоритм вернёт один из них

Динамика по топологическому порядку

Топологический порядок часто используют как “скелет” для динамического программирования на DAG.

Примерная схема:

получаем order

идём по вершинам слева направо

пересчитываем значения для соседей (потому что все зависимости уже обработаны)

Частые примеры:

самый длинный путь в DAG (в рёбрах или по весам)

время завершения проекта, если у задач есть длительности, а рёбра означают “после этого можно начинать”

Важно: “самый длинный путь” в произвольном графе — сложная задача, но на DAG она решается эффективно именно благодаря топологическому порядку.

Мини-пример: порядок сборки модулей

Пусть зависимости такие:

parser -> core

core -> app

utils -> app

Тогда граф:

Один из корректных ответов:

parser, utils, core, app

Другой корректный тоже возможен:

utils, parser, core, app

Оба соблюдают правило: каждая зависимость слева стоит раньше, чем вершина справа.

Частые ошибки

Путают направление зависимости: если “B зависит от A”, обычно рисуют ребро , потому что A должна быть раньше.

Не добавляют вершины, которые встречаются только как “правые концы” рёбер: тогда indegree и количество вершин будут посчитаны неверно.

Думают, что топологический порядок единственный: обычно он не единственный.

Что дальше

Топологическая сортировка — базовый инструмент для задач про зависимости и для динамики на DAG. В следующих практических задачах (и проектах) вы сможете комбинировать:

представление графа списком смежности

DFS/BFS для достижимости и компонент

топологический порядок для зависимостей и вычислений “слева направо”

Если захотите сравнить с библиотечным решением, посмотрите: NetworkX topological_sort.

Практикум: решение задач и оптимизация

Зачем нужен практикум

К этому моменту курса у вас есть все базовые инструменты:

представления графа (список рёбер, список смежности, матрица)

обходы BFS/DFS

кратчайшие пути (BFS для невзвешенных, Дейкстра, Беллман—Форд)

минимальные остовные деревья (Краскал, Прим)

топологическая сортировка (Кан, DFS)

На практике главная сложность часто не в том, чтобы знать алгоритм, а в том, чтобы быстро:

распознать тип задачи

выбрать правильную модель (ориентированность, веса)

собрать корректное и быстрое представление графа

не упереться в лимиты времени и памяти

Эта статья даёт рабочие шаблоны и чек-листы, которые помогают решать задачи “соревновательного” типа и писать быстрый код на Python.

!Блок-схема: как выбрать алгоритм по признакам задачи

Универсальная схема решения графовой задачи

Шаг: уточнить постановку

Проверьте признаки, которые “включают” нужный класс алгоритмов:

граф ориентированный или неориентированный

граф взвешенный или нет

возможны ли отрицательные веса

требуется путь между двумя вершинами или обработка всего графа

нужно ли соединить все вершины минимальной стоимостью (это про MST)

есть ли зависимости и нужен порядок выполнения (это про DAG и топологию)

Шаг: выбрать представление

Практическое правило для курса:

для почти всех алгоритмов берите список смежности

список рёбер удобен для Краскала и Беллмана—Форда

матрица смежности полезна редко и обычно только при малом числе вершин и частых запросах “есть ребро или нет”

Шаг: оценить ограничения и выбрать оптимизации

Обычно ограничения задают “формат” кода:

если и большие, важны линейные или почти линейные алгоритмы

если вершины — числа от 1 до , лучше использовать списки (они быстрее словарей)

если вершины — строки, почти всегда делайте перенумерацию в 0..n-1

Объяснение записи и :

— множество вершин графа

— количество вершин

— множество рёбер

— количество рёбер

Быстрый ввод и построение графа

Быстрый ввод

Для больших входных данных используйте буферизованный ввод.

Ссылка: sys — System-specific parameters and functions.

Шаблон: неориентированный невзвешенный граф (вершины 1..n)

Шаблон: ориентированный взвешенный граф (вершины 0..n-1)

Перенумерация вершин, если они не числа 0..n-1

Если вершины приходят строками, заведите отображение “имя -> индекс”.

Практический смысл: алгоритмы на списках (а не на словарях) обычно заметно быстрее.

Набор “узнаваемых” типов задач и готовых подходов

Достижимость, компоненты связности, проверка связности

Признаки:

граф невзвешенный

спрашивают “можно ли добраться” или “сколько компонент”

Двигатель:

BFS или DFS

Шаблон: количество компонент в неориентированном графе.

Ссылка на очередь: collections.deque.

Кратчайший путь в невзвешенном графе

Признаки:

веса отсутствуют или все рёбра “стоят одинаково”

нужно минимальное число рёбер

Двигатель:

BFS с массивом dist и массивом parent

Ключевая оптимизация:

хранить dist как список (если вершины 0..n-1 или 1..n)

Кратчайший путь во взвешенном графе без отрицательных весов

Признаки:

веса есть

все веса

Двигатель:

Дейкстра с кучей

Ссылка на кучу: heapq — Heap queue algorithm.

Оптимизационная деталь, которую нельзя забывать:

в heapq появляются “устаревшие” записи, их нужно отбрасывать проверкой текущей дистанции

Мини-шаблон (для вершин 0..n-1):

Кратчайший путь с отрицательными рёбрами и поиск отрицательного цикла

Признаки:

встречаются отрицательные веса

требуется обнаружить отрицательный цикл или гарантировать корректность ответа

Двигатель:

Беллман—Форд

Практическая заметка:

если граф большой, Беллман—Форд может не пройти по времени, поэтому важно читать условия: часто отрицательных весов нет, и достаточно Дейкстры

Минимальная стоимость соединения всех вершин

Признаки:

граф неориентированный

нужно “соединить всё”, минимизируя сумму весов

не спрашивают путь между конкретными двумя вершинами

Двигатель:

MST: Краскал (если удобно получить список рёбер) или Прим (если уже есть список смежности)

Типичная ошибка постановки:

пытаются решать MST алгоритмами кратчайших путей; MST и кратчайший путь — разные задачи

Зависимости, порядок выполнения работ, пререквизиты

Признаки:

ориентированный граф

нужно упорядочить вершины так, чтобы зависимости выполнялись раньше

Двигатель:

топологическая сортировка (Кан или DFS)

Проверка на цикл:

если топосорт не построился, зависимости цикличны

Оптимизация: что реально ускоряет Python-код на графах

Выбор контейнеров

Общее правило:

если вершины — числа в плотном диапазоне, используйте списки (list) вместо словарей (dict)

visited как список bool быстрее множества set

adj как список списков быстрее dict с ключами-вершинами

Когда всё же нужен set:

когда нужно быстро проверять “есть ли сосед” (to in neighbors)

когда нужно устранять дубли рёбер на входе

Снижение накладных расходов

Рабочие приёмы:

выносить часто используемые объекты в локальные переменные (например, adj_local = adj перед циклом)

избегать создания лишних списков внутри циклов

в DFS на больших графах предпочитать итеративный вариант, чтобы не упереться в рекурсию

Справка про ограничение рекурсии: sys.setrecursionlimit.

Типичные асимптотики, которые стоит помнить

Эти оценки помогают понять, “успеет ли” решение.

BFS/DFS на списке смежности:

Дейкстра с кучей:

Пояснение к :

возникает из-за операций в куче, где вставка и извлечение минимального работают примерно за логарифмическое время от числа элементов

Память: где можно неожиданно “взорваться”

Частые причины перерасхода памяти:

матрица смежности для больших (память растёт квадратично)

хранение графа дважды (например, и список смежности, и список рёбер без необходимости)

хранение больших структур parent и dist как словарей на вершинах-строках вместо перенумерации

Отладка и проверки корректности

Минимальные проверки, которые ловят большинство ошибок

для неориентированного графа: каждое ребро добавлено в обе стороны

для топологии: все вершины учтены, включая те, у которых нет исходящих рёбер

для Дейкстры: нет отрицательных весов

для восстановления пути: целевая вершина достижима (иначе путь отсутствует)

Тестовые случаи, которые стоит прогонять руками

одна вершина, ноль рёбер

две вершины, одно ребро

цикл из трёх вершин

несвязный граф (две компоненты)

для путей: вершина-цель недостижима

для топологии: простой цикл зависимостей длины 2

Мини-набор переиспользуемых функций для задач

Ниже набор функций, который часто удобно держать под рукой в одном файле и переиспользовать.

Замечание про restore_path:

это общий шаблон, но в реальной задаче нужно аккуратно обработать случай недостижимости; в BFS это dist[target] == -1, в Дейкстре это dist[target] == INF

Когда стоит брать готовую библиотеку

В учебных задачах полезно реализовывать алгоритмы вручную. В прикладных проектах часто разумнее использовать библиотеку, где много уже протестировано.

Если нужен готовый инструмент для анализа графов в Python, посмотрите NetworkX.

Итог

Практический навык в графах состоит из трёх частей:

правильно распознать тип задачи и выбрать алгоритм

быстро собрать граф в подходящем представлении

написать реализацию без “типовых” ошибок и с учётом ограничений

Если вы уверенно владеете шаблонами из этой статьи, то большая часть стандартных задач на графы становится вопросом аккуратной реализации, а не поиска идей.