Реализация

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

Здесь   — число вершин в первой доле,   — во второй доле,   — список рёбер из вершины   первой доли (т.е. список номеров вершин, в которые ведут эти рёбра из  ). Вершины в обеих долях занумерованы независимо, т.е. первая доля — с номерами  , вторая — с номерами  .

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

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

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

В основной программе сначала указывается, что текущее паросочетание — пустое (список   заполняется числами  ). Затем перебирается вершина   первой доли, и из неё запускается обход в глубину  , предварительно обнулив массив  .

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

int n, k;

vector < vector<int> > g;

vector<int> mt;

vector<char> used;

 

bool try_kuhn (int v) {

if (used[v]) return false;

used[v] = true;

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (mt[to] == -1 || try_kuhn (mt[to])) {

mt[to] = v;

return true;

}

}

return false;

}

 

int main() {

... чтение графа ...

 

mt.assign (k, -1);

for (int v=0; v<n; ++v) {

used.assign (n, false);

try_kuhn (v);

}

 

for (int i=0; i<k; ++i)

if (mt[i] != -1)

printf ("%d %d\n", mt[i]+1, i+1);

}

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