← вся теориятеория к собесу · Алгоритмы и структуры данных

Алгоритмы на графах: обходы и кратчайшие пути

Зачем это спрашивают

Графовые алгоритмы проверяют умение выбирать по свойствам задачи: есть ли веса, бывают ли они отрицательными, нужен один путь или все сразу. Реализацию Флойда наизусть не спрашивают почти никогда, а вот таблицу выбора - постоянно.

Типовые формулировки: «как найдёшь кратчайший путь?», «можно ли пройти все курсы?», «есть ли в графе цикл?».

// Автозавал темы один и тот же годами: Дейкстра на отрицательных рёбрах. Знать, что она ломается, мало - надо уметь объяснить, почему именно.

Кратчайшие пути: таблица выбора

Невзвешенный граф - обход вширь, его слои и есть расстояния. Неотрицательные веса - Дейкстра с кучей, O((V + E) log V). Есть отрицательные рёбра - Беллман-Форд, O(V·E), он заодно умеет обнаруживать отрицательные циклы. Нужны расстояния между всеми парами сразу - Флойд-Уоршелл, O(V³), если число вершин позволяет.

Теперь про то, почему Дейкстра ломается, - это спрашивают чаще самого алгоритма. Она жадная: извлекла вершину из кучи, объявила расстояние до неё окончательным и больше к ней не возвращается. Работает это ровно потому, что рёбра неотрицательные: любой обходной путь только длиннее.

Контрпример считается за минуту. Пусть из A в B ребро весом 2, из A в C весом 5, а из C в B весом −4. Дейкстра извлечёт B с расстоянием 2 и закроет его. А настоящий кратчайший путь A → C → B стоит 5 − 4 = 1. Ответ неверный, и никакой ошибки алгоритм не выдаст.

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

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

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

Цикл в ориентированном графе ищут обходом вглубь с тремя цветами. Белый - вершину ещё не трогали. Серый - вершина в текущем пути, мы в неё вошли и ещё не вышли. Чёрный - вершина полностью обработана, из неё уже вернулись. Правило: ребро, ведущее в СЕРУЮ вершину, означает цикл.

Почему не хватает обычного множества посещённых, видно на ромбе: A ведёт в B и в C, а B и C оба ведут в D. Обходя, мы придём в D дважды, и плоская проверка «уже посещена» объявит цикл, которого нет. С цветами всё честно: во второй раз D окажется чёрной, то есть давно закрытой, а не серой, и цикл не засчитается.

Топологическая сортировка - выстроить вершины так, чтобы каждая зависимость шла раньше зависимого. Способа два. Обратный пост-порядок того же обхода вглубь: закончил с вершиной - положил в начало списка. Или алгоритм Кана: снимаем вершины, в которые не входит ни одного ребра, после каждого снятия пересчитываем степени соседей. Если сняли не все - в графе цикл, и порядка не существует.

// Задачи «можно ли пройти все курсы», «в каком порядке собирать модули», «почему билд зациклился» - это топологическая сортировка, переодетая в продуктовую формулировку. Слово «зависимость» в условии - почти прямая подсказка.

Система непересекающихся множеств

DSU (disjoint set union), она же union-find, отвечает на вопрос «эти две вершины в одной компоненте?» почти за константу. Устроена как лес деревьев, по одному на компоненту, где каждый узел помнит только своего родителя, а корень служит именем всей компоненты.

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

Применения: динамическая связность, когда рёбра приходят по одному и пересчитывать обход после каждого дорого; поиск цикла в неориентированном графе (ребро внутри уже объединённой компоненты и есть цикл); построение минимального остовного дерева алгоритмом Крускала. Остовное дерево - это набор рёбер, связывающий все вершины без циклов, а минимальное - самый дешёвый из таких наборов.

// Против обхода DSU выигрывает именно на динамике. Если граф задан целиком и не меняется, компоненты проще найти одним обходом. Если рёбра добавляются по ходу - обход придётся запускать заново после каждого, а DSU обновляется за амортизированную константу.

Как отвечать: «Как найдёшь кратчайший путь и от чего зависит выбор алгоритма?»

От свойств графа, и я бы прошёл по ним по порядку. Граф невзвешенный - обход вширь, его слои и есть кратчайшие расстояния. Веса неотрицательные - Дейкстра с кучей: жадно закрываем ближайшую вершину и больше к ней не возвращаемся. На отрицательных рёбрах эта жадность ломается: до закрытой вершины позже находится путь дешевле - через обходное отрицательное ребро, поэтому там Беллман-Форд, который вдобавок обнаруживает отрицательные циклы. Нужны все пары сразу и вершин немного - Флойд-Уоршелл за куб. И одна практическая деталь: в Дейкстре вершина закрывается при извлечении из кучи, а не при добавлении в неё. Перепутать эти два момента значит получить неверные расстояния без единой ошибки в коде.

Полное дерево выбора, объяснённая причина поломки Дейкстры и деталь реализации, которая всплывает только у тех, кто её писал. Теоретик перечислит алгоритмы, но не назовёт момент закрытия вершины.

На чём валят

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

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 23, остальные разбираются в тренажёре.

#graph_algorithms1 / 5
Дейкстра дал неверные кратчайшие пути на графе с отрицательными весами рёбер. Почему и что берут вместо неё?
A)Дейкстра не работает с направленными графами — нужен неориентированный вариант
B)Дело в приоритетной очереди: заменив кучу на простой массив, Дейкстру можно корректно применять к отрицательным весам
C)Дейкстра жадно фиксирует вершину и не пересматривает; отрицательное ребро это ломает — берут Беллмана-Форда
D)Отрицательные веса нужно просто взять по модулю перед запуском
показать ответ и разбор
+C)Дейкстра жадно фиксирует вершину и не пересматривает; отрицательное ребро это ломает — берут Беллмана-Форда
// разбор: Дейкстра жадно фиксирует ближайшую вершину, полагая, что более короткого пути к ней уже не найдётся — это верно лишь при неотрицательных весах. Отрицательное ребро может удешевить путь к уже закрытой вершине, и алгоритм даст неверный ответ. Беллман-Форд релаксирует все рёбра V−1 раз, работает с отрицательными весами и обнаруживает отрицательные циклы (за счёт O(V·E) вместо O(E log V)).
#graph_algorithms2 / 5
Структура «система непересекающихся множеств» (union-find / DSU) — для чего и почему она быстрая?
A)Для сортировки вершин графа по компонентам за O(n log n)
B)Для компактного хранения кратчайших путей между всеми парами вершин с доступом к расстоянию за постоянное время
C)Для поиска минимума в множестве за постоянное время
D)Отвечать «в одном ли множестве два элемента» и сливать множества почти за константу (сжатие путей + ранги)
показать ответ и разбор
+D)Отвечать «в одном ли множестве два элемента» и сливать множества почти за константу (сжатие путей + ранги)
// разбор: DSU поддерживает две операции: find (представитель множества элемента) и union (слить два множества). Сжатие путей укорачивает деревья при каждом find, а объединение по рангу подвешивает меньшее дерево под большее — вместе они дают амортизированную сложность почти O(1) (α(n), обратная Аккермана). Отсюда её роль в алгоритме Краскаля (MST) и в подсчёте компонент связности.
#graph_algorithms3 / 5
Как за один обход обнаружить цикл в ОРИЕНТИРОВАННОМ графе?
A)Обычной пометкой посещённых, как в неориентированном графе: первое же повторное попадание в вершину означает цикл
B)Тремя состояниями вершины (белая/серая/чёрная): ребро в «серую», что в стеке рекурсии, — это цикл
C)Подсчётом числа рёбер: если их больше числа вершин, есть цикл
D)Сортировкой вершин по степени
показать ответ и разбор
+B)Тремя состояниями вершины (белая/серая/чёрная): ребро в «серую», что в стеке рекурсии, — это цикл
// разбор: В ориентированном графе простой пометки visited мало: встретить уже посещённую вершину можно и без цикла (перекрёстное ребро). Нужны три цвета: серый — вершина в текущем пути DFS (в стеке рекурсии), чёрный — полностью обработана. Ребро в СЕРУЮ вершину означает возврат к предку по текущему пути — обратное ребро, то есть цикл. Ребро в чёрную циклом не является.
#graph_algorithms4 / 5
Чем отличаются алгоритмы Прима и Краскала для минимального остовного дерева (MST)?
A)Прим вычисляет кратчайшие пути от стартовой вершины, а Краскал ищет и разрывает циклы, оставляя остовное дерево
B)Это один алгоритм под двумя именами
C)Прим растит дерево от вершины минимальными рёбрами; Краскал сортирует рёбра и берёт без цикла (union-find)
D)Прим работает только на деревьях, Краскал — только на циклах
показать ответ и разбор
+C)Прим растит дерево от вершины минимальными рёбрами; Краскал сортирует рёбра и берёт без цикла (union-find)
// разбор: Оба строят остов минимального суммарного веса, но по-разному. Прим растит одно дерево от стартовой вершины, на каждом шаге присоединяя самое лёгкое ребро, выходящее наружу (удобно с кучей, хорош для плотных графов). Краскал рассматривает рёбра по возрастанию веса и берёт ребро, если оно не создаёт цикл (проверка через DSU) — удобно для разреженных графов. Результат по весу одинаков.
#graph_algorithms5 / 5
Как проверить, что граф двудольный (bipartite), обходом?
A)Достаточно подсчитать вершины: граф двудольный тогда и только тогда, когда их количество чётно
B)Проверить, что нет ни одного цикла вообще
C)Убедиться, что все вершины имеют одинаковую степень
D)2-раскраска обходом: соседям противоположный цвет; конфликт означает нечётный цикл — не двудольный
показать ответ и разбор
+D)2-раскраска обходом: соседям противоположный цвет; конфликт означает нечётный цикл — не двудольный
// разбор: Граф двудольный, если вершины можно разбить на два класса без рёбер внутри класса. Проверяют 2-раскраской: обходом присваивают старту цвет 0, каждому соседу — противоположный. Конфликт (сосед уже покрашен в тот же цвет) означает нечётный цикл — двудольности нет. Работает за O(V+E) и заодно строит само разбиение на доли.

дальше

Теорию прочитали. Навык ставится повторением

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

Открыть тренажёр Вся тема: Алгоритмы и структуры данных