Алгоритм Хопкрофта–Карпа: паросочетание в двудольном графе за O(E√V)

Алгоритм Хопкрофта–Карпа: как BFS-слои и DFS находят сразу пачку кратчайших увеличивающих цепей, откуда O(E√V), код на Python и замеры против алгоритма Куна.

12 мин чтенияалгоритмы · графы · паросочетания · python

Коротко

ПараметрЗначение
Задачамаксимальное паросочетание в двудольном графе
СложностьO(EV)O(E\sqrt{V}) по времени, O(V+E)O(V + E) по памяти
Идеяфаза = BFS строит слои, DFS по слоям находит максимальный набор непересекающихся кратчайших увеличивающих цепей
Число фазне больше 2V2\sqrt{V}
Когда братьграф на десятки и сотни тысяч вершин, где алгоритм Куна за O(VE)O(VE) не укладывается в лимит

Базу — что такое паросочетание, увеличивающая цепь и теорема Бержа — разбирает статья про алгоритм Куна. Здесь эти понятия считаются известными, а речь пойдёт о том, как ускорить поиск цепей.

Почему Кун медленный

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

Есть две беды:

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

Хопкрофт и Карп в 1973 году лечат обе: за один проход по графу ищем много цепей, и все они кратчайшие.

Идея: фазы

Алгоритм работает фазами. Каждая фаза состоит из двух шагов.

BFS: строим слои. Стартуем одновременно из всех свободных вершин левой доли — это слой 0. Из левой вершины идём по любому ребру в правую. Если правая вершина свободна, нашли конец увеличивающей цепи. Если занята, переходим по ребру паросочетания в её левую пару — это следующий слой. BFS даёт каждой левой вершине dist — номер слоя. Как только встретилась свободная правая вершина, запоминаем длину limit и глубже не идём: нас интересуют только кратчайшие цепи.

DFS: собираем цепи. Из каждой свободной левой вершины запускаем DFS, который ходит только вниз по слоям: из вершины слоя kk можно перейти лишь в вершину слоя k+1k+1. Нашли цепь — сразу инвертируем её. Вершину, из которой цепь не нашлась, помечаем тупиком (dist = INF), чтобы в этой фазе больше туда не заходить.

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

Алгоритм останавливается, когда BFS не дошёл ни до одной свободной правой вершины. По теореме Бержа паросочетание тогда максимально.

Реализация

Левая доля — вершины 0..n_left-1, правая — 0..n_right-1, граф задан списками смежности для левой доли.

from collections import deque INF = float('inf') def hopcroft_karp(adj: list[list[int]], n_right: int) -> tuple[int, list[int]]: """adj[u] — соседи вершины u левой доли (номера 0..n_right-1). Возвращает (размер паросочетания, match_left).""" n_left = len(adj) match_left = [-1] * n_left # u -> v или -1 match_right = [-1] * n_right # v -> u или -1 dist = [INF] * n_left ptr = [0] * n_left # с какого ребра продолжать DFS в этой фазе def bfs() -> int: """Строит слои. Возвращает длину кратчайшего пути до свободной правой вершины (в шагах по левой доле) или INF, если путей нет.""" queue = deque() for u in range(n_left): ptr[u] = 0 if match_left[u] == -1: dist[u] = 0 queue.append(u) else: dist[u] = INF limit = INF while queue: u = queue.popleft() if dist[u] >= limit: continue # глубже кратчайшей длины не идём for v in adj[u]: w = match_right[v] if w == -1: limit = min(limit, dist[u] + 1) elif dist[w] == INF: dist[w] = dist[u] + 1 queue.append(w) return limit def dfs(u: int, limit: int) -> bool: while ptr[u] < len(adj[u]): v = adj[u][ptr[u]] ptr[u] += 1 w = match_right[v] if (w == -1 and dist[u] + 1 == limit) or ( w != -1 and dist[w] == dist[u] + 1 and dfs(w, limit) ): match_left[u] = v match_right[v] = u return True dist[u] = INF # тупик: в этой фазе сюда не возвращаемся return False size = 0 while (limit := bfs()) != INF: for u in range(n_left): if match_left[u] == -1 and dfs(u, limit): size += 1 return size, match_left adj = [[0, 1], [0], [1, 2], [2, 3]] print(hopcroft_karp(adj, 4)) # (4, [1, 0, 2, 3])

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

Что делает каждая деталь:

  • limit. Свободную правую вершину DFS принимает, только если стоит ровно на кратчайшей длине dist[u] + 1 == limit. Без этого условия DFS подбирал бы и более длинные цепи, и оценка числа фаз перестала бы работать.
  • dist[w] == dist[u] + 1. Это то, что делает DFS «слоистым»: двигаемся строго на один слой вниз.
  • dist[u] = INF при неудаче. Если из u цепь не нашлась, она не найдётся до конца фазы. Без этой пометки DFS снова и снова заходил бы в тупиковые поддеревья.
  • ptr[u]. Ребро, которое уже не сработало, в этой фазе не сработает и дальше. Указатель гарантирует, что каждое ребро просматривается за фазу не больше одного раза, — именно отсюда O(E)O(E) на фазу.

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

Разбор на примере

Граф из кода выше: левые u0..u3, правые v0..v3.

u0: v0, v1
u1: v0
u2: v1, v2
u3: v2, v3

Фаза 1. Все левые вершины свободны, все в слое 0. Любая из них за один шаг достаёт до свободной правой вершины, поэтому limit = 1: ищем цепи из одного ребра. DFS идёт по вершинам по порядку:

  • u0 берёт v0;
  • u1 хочет v0, но та уже занята, а её пара u0 стоит в слое 0, не в слое 1. Других рёбер у u1 нет — тупик;
  • u2 берёт v1;
  • u3 берёт v2.

После фазы паросочетание размера 3: u0-v0, u2-v1, u3-v2. Фактически первая фаза — это жадная инициализация, которую для Куна приходится писать руками.

Фаза 2. Свободна только u1, она в слое 0. BFS:

слой 0: u1
        u1 → v0 (занята u0)  ⇒ u0 в слое 1
слой 1: u0
        u0 → v1 (занята u2)  ⇒ u2 в слое 2
слой 2: u2
        u2 → v2 (занята u3)  ⇒ u3 в слое 3
слой 3: u3
        u3 → v3 (свободна)   ⇒ limit = 4

DFS из u1 спускается по слоям и находит цепь u1 → v0 ⇒ u0 → v1 ⇒ u2 → v2 ⇒ u3 → v3. После инверсии: u1-v0, u0-v1, u2-v2, u3-v3, размер 4.

Фаза 3. Свободных левых вершин нет, BFS не находит ни одной цепи — конец.

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

Почему O(EV)O(E\sqrt{V})

Одна фаза — это BFS и серия DFS, где каждое ребро смотрится не больше одного раза. Итого O(V+E)O(V + E) на фазу. Остаётся показать, что фаз мало.

Опираемся на два факта (доказываются через симметрическую разность паросочетаний):

  1. Длина кратчайшей увеличивающей цепи после каждой фазы строго растёт. Фаза выбирает максимальный набор непересекающихся кратчайших цепей. Любая цепь той же длины, оставшаяся после фазы, пересекалась бы с найденными, а такая цепь обязана быть длиннее.
  2. Если MM — текущее паросочетание, а M^_ — максимальное, то в графе есть |M^_| - |M| непересекающихся по вершинам увеличивающих цепей. Они получаются из компонент симметрической разности M⊕M∗M \oplus M^*.

Теперь сам аргумент. Пройдём первые V\sqrt{V} фаз. Кратчайшая цепь растёт каждую фазу, поэтому после них все увеличивающие цепи длиннее V\sqrt{V} рёбер. По факту 2 существует ∣M∗∣−∣M∣|M^*| - |M| непересекающихся цепей, каждая длиннее V\sqrt{V}, а всего в графе VV вершин. Значит, их не больше V\sqrt{V}:

∣M∗∣−∣M∣≤VV=V.|M^*| - |M| \le \frac{V}{\sqrt{V}} = \sqrt{V}.

Каждая следующая фаза находит хотя бы одну цепь, поэтому оставшихся фаз не больше V\sqrt{V}. Всего фаз O(V)O(\sqrt{V}), итог:

O(V (V+E))=O(EV),O\big(\sqrt{V}\,(V + E)\big) = O(E\sqrt{V}),

если изолированные вершины выброшены и E≥V/2E \ge V/2.

На практике фаз ещё меньше. На случайном графе из 20 000 + 20 000 вершин, где у каждой левой вершины три случайных соседа, алгоритм завершился за 10 фаз, хотя граница 2V2\sqrt{V} для V=40 000V = 40\,000 равна 400.

Замеры: Хопкрофт–Карп против Куна

Обе реализации на чистом Python, Кун — из статьи про алгоритм Куна с массивами вместо словарей. Измерения на одной машине, абсолютные числа зависят от железа, важно соотношение.

ГрафОтветКунКун + жадная инициализацияХопкрофт–Карп
случайный, 20 000+20 00020\,000 + 20\,000, по 3 ребра18 753≈ 17 с≈ 13,6 с≈ 0,3 с
«лесенка» ui→v0..viu_i \to v_0..v_i, n=3000n = 30003000≈ 87 с≈ 0,1 с≈ 0,8 с

Из таблицы видно две вещи.

  • На случайном графе разница — в 40–50 раз даже с оптимизированным Куном. Жадная инициализация закрывает основную массу пар, но на оставшиеся ~1000 Кун каждый раз запускает почти полный обход графа.
  • «Лесенка» — плохой случай для Куна без жадной фазы: каждая новая вершина сначала пытается взять v0 и устраивает цепочку переселений через все предыдущие. Жадная инициализация решает этот граф сразу, а Хопкрофт–Карп справляется за одну фазу (его первая фаза и есть жадный проход), хотя здесь он медленнее из-за накладных расходов и O(n2)O(n^2) рёбер.

Вывод: если граф небольшой или лимит щедрый, Кун с жадной инициализацией короче и достаточен. Если VV и EE порядка 10510^5, нужен Хопкрофт–Карп.

Глубина рекурсии

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

import sys import threading sys.setrecursionlimit(1 << 20) threading.stack_size(256 * 1024 * 1024) # 256 МБ под стек def main(): ... # чтение графа и вызов hopcroft_karp threading.Thread(target=main).start()

Альтернатива — переписать DFS на явный стек. Код становится длиннее примерно вдвое, зато не зависит от лимитов интерпретатора. На C++ и Java обычно хватает рекурсии, если поднять размер стека или граф не вырожденный.

Хопкрофт–Карп как частный случай Диница

Если свести паросочетание к максимальному потоку — исток соединён со всеми левыми вершинами, все правые со стоком, все пропускные способности равны 1 — и запустить на этой сети алгоритм Диница, получится ровно Хопкрофт–Карп. BFS строит слоистую сеть, DFS ищет блокирующий поток, а блокирующий поток в единичной сети — это и есть максимальный набор непересекающихся кратчайших путей.

Это полезно знать по двум причинам. Во-первых, если у вас в шаблонах уже есть Диниц, отдельный Хопкрофт–Карп можно не писать: на единичных сетях Диниц сам работает за O(EV)O(E\sqrt{V}). Во-вторых, на собеседовании это хороший ответ на вопрос «откуда берётся корень»: оценка Карзанова и Эвена–Тарьяна для единичных сетей доказывается тем же рассуждением про длину кратчайшего пути.

Типичные ошибки

Нет отсечения по limit. BFS продолжает искать после того, как нашёл свободную правую вершину, а DFS принимает любую свободную правую вершину. Ответ будет правильным, но цепи уже не обязательно кратчайшие, и гарантия O(V)O(\sqrt{V}) фаз теряется.

DFS игнорирует слои. Если вместо dist[w] == dist[u] + 1 проверять что-то вроде «ещё не посещали», получится Кун с BFS-прологом, который ничего не ускоряет.

Тупики не помечаются. Без dist[u] = INF при неудаче одна фаза может стоить O(VE)O(VE), и весь смысл пропадает.

Нет указателя на ребро. Вариант без ptr встречается часто и на практике обычно работает быстро, но оценка O(E)O(E) на фазу для него не гарантирована: вершину, через которую уже прошла цепь, DFS может посетить снова и заново перебрать её рёбра.

Сброс состояния между фазами. dist и ptr пересчитываются каждой фазой, а match_left и match_right — нет: паросочетание накапливается.

Недвудольный граф. Как и Кун, алгоритм корректен только для двудольных графов. Сначала стоит проверить двудольность и раскрасить вершины в две доли. Для общих графов нужен алгоритм Эдмондса, а его быстрый аналог — алгоритм Микали–Вазирани за то же O(EV)O(E\sqrt{V}) — заметно сложнее.

Где встречается на собеседованиях

Сам Хопкрофт–Карп на обычном алгоритмическом интервью почти не спрашивают: там двудольного паросочетания хватает в версии Куна, а размеры входов маленькие. Он нужен в трёх ситуациях:

  • Олимпиадные задачи и контесты, где V,E∼105V, E \sim 10^5: распределение, покрытие клеток доминошками, минимальное вершинное покрытие через теорему Кёнига на большом графе.
  • Вопрос «а можно быстрее?» после решения задачи через Куна. Хороший ответ: «да, Хопкрофт–Карп за O(EV)O(E\sqrt{V}) — ищем за фазу максимальный набор кратчайших цепей, длина кратчайшей цепи растёт, поэтому фаз O(V)O(\sqrt{V})».
  • Позиции с упором на алгоритмы — оптимизация, логистика, планирование. Там задачи о назначениях реальные и большие, а знание, когда хватает паросочетания, а когда нужен венгерский алгоритм для взвешенного случая, ценится.

Примеры задач с LeetCode, которые решаются через двудольное паросочетание: «Maximum Number of Accepted Invitations» (1820) и «Maximum Students Taking Exam» (1349, через максимальное независимое множество и теорему Кёнига). Размеры там небольшие, и Кун проходит, но это хороший полигон, чтобы отладить и Хопкрофта–Карпа.

Что запомнить

  • Хопкрофт–Карп ищет те же увеличивающие цепи, что и Кун, но пачками и только кратчайшие.
  • Фаза: BFS из всех свободных левых вершин строит слои и находит длину кратчайшей цепи; DFS ходит только вниз по слоям, тупики помечает, каждое ребро смотрит один раз.
  • Длина кратчайшей цепи растёт с каждой фазой, поэтому фаз O(V)O(\sqrt{V}), а всё вместе — O(EV)O(E\sqrt{V}).
  • Первая фаза бесплатно делает жадную инициализацию.
  • Это алгоритм Диница на единичной сети; если Диниц уже есть в шаблонах, он даст ту же асимптотику.
  • Для графов на сотни вершин хватит Куна; на 10510^5 без Хопкрофта–Карпа не обойтись.

Потренироваться в спокойной обстановке

Все задачи