Алгоритм Хопкрофта-Карпа: паросочетание по фазам

Как назначить как можно больше исполнителей на подходящие задачи, если у каждого есть свой список допустимых вариантов? Нарисуем исполнителей и задачи в двух долях графа, а допустимые назначения обозначим рёбрами. Нужно выбрать как можно больше рёбер без общих концов.
Алгоритм Хопкрофта-Карпа решает эту задачу для невзвешенного двудольного графа. Его особенность - поиск нескольких кратчайших увеличивающих цепей за одну фазу. В инструменте ниже можно пройти две фазы на небольшом графе и увидеть, какие пары меняются.
Что считается ответом
Пусть - двудольный граф: каждое ребро соединяет вершину левой доли с вершиной правой доли . Паросочетание - множество рёбер, никакие два из которых не имеют общей вершины. Занятая вершина входит в одно выбранное ребро; остальные вершины свободны.
Максимальное паросочетание имеет наибольшее возможное число рёбер. Оно не обязательно покрывает все вершины и не обязательно единственно. Не путайте его с нерасширяемым: к последнему нельзя просто добавить одно ребро, но можно заменить несколько выбранных рёбер и получить больше пар. Такой обмен и организует алгоритм.
Например, если пара А–1 уже выбрана, а Б связана только с 1, простое добавление пары для Б невозможно. Но при наличии ребра А–2 можно заменить А–1 на А–2 и Б–1. Вместо одной пары получаются две. Подробное введение в чередующиеся пути есть в статье об алгоритме Куна; здесь главное - как объединить поиск таких путей в фазы.
Почему несколько цепей за фазу
Увеличивающая цепь начинается в свободной вершине , заканчивается в свободной вершине и чередует рёбра вне и рёбра из . Первое и последнее рёбра в не входят. Если поменять принадлежность всех рёбер цепи на противоположную, внутренние вершины сохранят по одной паре, а оба свободных конца станут занятыми. Размер паросочетания вырастет на единицу.
В одной фазе Хопкрофт-Карп сначала находит длину кратчайшей увеличивающей цепи, затем выбирает набор таких цепей, не пересекающихся по вершинам. Каждую можно инвертировать независимо. Набор должен быть максимальным по включению: после выбора нельзя добавить ещё одну непересекающуюся кратчайшую цепь. Он не обязан иметь наибольшее число цепей среди всех возможных наборов.
BFS: где находятся кратчайшие цепи
В начале фазы поиск в ширину стартует одновременно из всех свободных вершин левой доли. Он идёт из левой доли вправо по рёбрам вне паросочетания, а из занятой правой вершины возвращается влево по её единственному ребру из . Так строятся слои чередующихся путей.
Когда BFS впервые достигает свободной правой вершины, известна длина кратчайшей увеличивающей цепи. Однако обработку остальных вершин предыдущего слоя нужно завершить: другие свободные правые вершины могут лежать на той же глубине. Более длинные пути в текущей фазе не нужны.
При реализации удобно хранить расстояние только для левых вершин и условного конечного состояния. Один шаг расстояния тогда соответствует переходу через правую вершину к следующей левой либо к свободному правому концу. Для полного пути реальная длина в рёбрах равна , где - расстояние до конечного состояния. Это соглашение отличается от подсчёта каждого ребра отдельно, но задаёт те же слои.
DFS: какие цепи выбрать
После BFS поиск в глубину запускают из свободных вершин . DFS продолжает путь только по рёбрам, согласованным с построенными слоями, и достигает свободного правого конца только на найденной кратчайшей глубине. При успехе пары обновляются вдоль пути; при неудаче вершину помечают недоступной до следующей фазы, чтобы повторно не перебирать её бесполезные продолжения.
Абстрактная схема такова:
M = пустое паросочетание
пока BFS находит кратчайшую длину увеличения:
для каждой свободной вершины u слева:
DFS из u по слоям BFS
при успехе инвертировать найденную цепь
вернуть M
DFS после каждого успеха учитывает обновлённые пары. В стандартной реализации слоистый поиск и пометки обеспечивают набор вершинно-непересекающихся кратчайших цепей и линейную работу за фазу. BFS затем строят заново: новые пары меняют допустимое чередование. Обычный поиск в ширину полезен для понимания слоёв, но здесь направления переходов дополнительно зависят от текущего . В отличие от алгоритма Дейкстры, который ищет кратчайшие пути по неотрицательным весам, BFS этой задачи считает число рёбер в чередующихся путях.
Пример: четыре исполнителя и четыре задачи
Возьмём доли и . Возможные назначения:
А: 1, 2 Б: 1 В: 3, 4 Г: 3
Начинаем с пустого и перебираем соседей в указанном порядке. На первой фазе кратчайшие цепи состоят из одного ребра. DFS выбирает А–1 и В–3; Б и Г остаются свободными. Получается две пары. Другой порядок может дать другое промежуточное паросочетание и даже завершить этот пример за одну фазу.
На второй фазе свободные Б и Г начинают две цепи длины три: и . Средние рёбра уже входят в , остальные пока нет. Цепи не имеют общих вершин, поэтому после их инверсии получаем . Это четыре пары; больше невозможно, поскольку в каждой доле всего четыре вершины.

Первая фаза добавила две пары, вторая - ещё две. Ползунок выше показывает эти же состояния; длины цепей относятся к началу соответствующей фазы. Золотые рёбра на графике обозначают выбранные пары, а не все допустимые назначения.
Как восстановить ответ
Для каждой вершины достаточно хранить её текущего партнёра или специальное значение для свободной вершины. Практично поддерживать два массива: партнёра каждой левой вершины и партнёра каждой правой. После инверсии они должны описывать одни и те же рёбра с двух сторон. В конце можно пройти по левому массиву и вывести все пары, у которых партнёр задан.
Проверить конкретный результат проще, чем повторять весь поиск: убедитесь, что каждое выбранное ребро действительно есть во входном графе и что никакая вершина не встречается дважды. Эти условия подтверждают допустимость, но не максимальность. Для последней нужен отдельный аргумент: отсутствие увеличивающей цепи или, как в нашем примере, совпадение числа пар с верхней границей по размеру меньшей доли.
Откуда берётся оценка сложности
Обозначим , . Одна фаза BFS и DFS занимает при списках смежности и корректном исключении повторного бесполезного просмотра. После максимального набора кратчайших цепей длина кратчайшей увеличивающей цепи строго возрастает.
Первые фаз можно ограничить просто числом разных длин. Затем кратчайшая цепь уже имеет длину порядка . Рассмотрим симметрическую разность текущего и оптимального паросочетаний: в ней найдётся не меньше разницы их размеров вершинно-непересекающихся увеличивающих цепей. Каждая содержит порядка вершин, поэтому недостающих до оптимума пар осталось . Каждая следующая фаза добавляет хотя бы одну пару, значит и таких фаз .
Итого получается времени и памяти для графа и рабочих массивов. После удаления изолированных вершин часто пишут более компактно . Эта оценка приведена в оригинальной работе Хопкрофта и Карпа. Для сравнения, типичная оценка последовательного поиска цепей алгоритмом Куна - .
Когда применять алгоритм
Он подходит для невзвешенных назначений: студентам подбирают проекты, заявкам - доступные интервалы, заказам - совместимые машины. Рёбра должны означать именно допустимость пары, а цель - максимальное количество пар. Если важна суммарная стоимость или предпочтения, нужна другая постановка, например венгерский алгоритм.
Ту же задачу можно свести к единичному потоку: добавить исток к левым вершинам, сток к правым и поставить пропускную способность 1 на каждое ребро. Связь с остаточными путями помогает сопоставить подход с алгоритмом Эдмондса-Карпа, хотя Хопкрофт-Карп использует специальную структуру двудольного паросочетания и работает фазами. При планировании большого графа удобно заранее оценить объём хранения: список смежности занимает место пропорционально числу вершин и допустимых пар.
Частые ошибки
- Останавливать BFS на первой найденной правой вершине. Нужно учесть и другие кратчайшие пути той же глубины.
- Искать DFS произвольные увеличивающие пути. В фазе допустимы только переходы по слоям к кратчайшим свободным концам.
- Считать максимальный по включению набор цепей обязательно наибольшим по числу. Для гарантии алгоритма достаточно первого свойства.
- Смешивать паросочетание с покрытием всех вершин. Максимальный ответ может оставлять вершины свободными.
- Игнорировать обновление пар и пометки неудачных вершин. Это нарушает корректность обхода или заявленную стоимость фазы.
FAQ
Что происходит, если увеличивающая цепь не найдена?
Алгоритм останавливается: по теореме Бержа отсутствие увеличивающей цепи равносильно максимальности текущего паросочетания.
Обязательно ли граф должен быть двудольным?
Да, для описанной здесь версии. В общем графе возникают нечётные циклы, для работы с которыми нужны дополнительные приёмы, например сжатие цветков.
Можно ли получить разные ответы на одном графе?
Да. Порядок вершин и соседей влияет на выбранные цепи. При корректной реализации итоговые паросочетания могут различаться рёбрами, но их размер одинаков и максимален.
Коротко
Хопкрофт-Карп чередует BFS для определения кратчайших увеличивающих цепей и DFS для выбора их непересекающегося набора. Инверсия каждой цепи добавляет одну пару, а число фаз ограничено . Метод особенно удобен, когда нужно максимизировать число совместимых назначений в большом двудольном графе.
Читайте также

Алгоритм Куна: как найти максимальное паросочетание
Алгоритм Куна шаг за шагом: ищем увеличивающие цепи обычным DFS и находим максимальное паросочетание в двудольном графе за O(V·E), с разбором идеи и сложности.

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

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

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

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

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