Алгоритм поиска максимального паросочетания в двудольном графе (реализация на C++)

C++   27 сентября 2015  Автор статьи:  

Задан неориентированный двудольный граф G = (V, E), имеющий N_{1} вершин в первой доли, N_{2} вершин во второй доли и M ребер. Требуется найти в нем максимальное паросочетание (множество попарно несмежных рёбер, то есть рёбер, не имеющих общих вершин наибольшей мощности).
Исходный двудольный граф G удобно представлять в памяти ЭВМ списком смежности adj, храня для каждой вершины первой доли v список adj[v] смежных с ней вершин второй доли.


vector *adj; //список смежности
vector used; //массив для хранения информации о пройденных и не пройденных вершинах
int mtSize = 0; //размер максимального паросочетания
vector mt; //массив для хранения ребер, образующих максимальное паросочетание

В качестве списка смежности для представления графа на языке C++ удобно использовать массив, каждый элемент которого является структурой данных vector<int>.

В приведенной ниже реализации данные считываются и выводятся в консоль.

Входные данные

В первой строке входного файла задано три целых числа: N_{1} (1 \le N_{1} \le 10^3) – количество вершин в первой доли графа, N_{2} (1 \le N_{2} \le 10^3) – количество вершин во второй доли графа и M (1 \le M \le N_{1} * N_{2}) – количество ребер графа соответственно. Каждая из следующих M строк содержит описание ребра графа парами вершин: первое число — вершина первой доли, второй число — вершина второй доли. Первое число находятся в диапазоне от 1 до N_{1}, второе число – в диапазоне от 1 до N_{2}.

Выходные данные

В первой строке выходного файла показано количество ребер в некотором максимальном паросочетании исходного двудольного графа G = (V, E). Далее выводятся ребра этого максимального паросочетания, заданные парами вершин. Первая вершина в паре является вершиной первой доли, вторая вершина — вершиной второй доли соответственно.


#include
#include

using namespace std;

int n1; //количество вершин в первой доле графа
int n2; //количество вершин во второй доле графа
int m; //количество ребер в графе
vector *adj; //список смежности
vector used; //массив для хранения информации о пройденных и не пройденных вершинах
int mtSize = 0; //размер максимального паросочетания
vector mt; //массив для хранения ребер, образующих максимальное паросочетание

//алгоритм Куна поиска максимального паросочетания
bool kuhn(int v) {
//если вершина является пройденной, то не производим из нее вызов процедуры
if (used[v]) {
return false;
}
used[v] = true; //помечаем вершину первой доли, как пройденную
//просматриваем все вершины второй доли, смежные с рассматриваемой вершиной первой доли
for (int i = 0; i < adj[v].size(); ++i) { int w = adj[v][i]; //нашли увеличивающую цепь, добавляем ребро (v, w) в паросочетание if (mt[w] == -1 || kuhn(mt[w])) { mt[w] = v; return true; } } return false; } //процедура считывания входных данных с консоли void readData() { //считываем количество вершин в первой и второй доли и количество ребер графа scanf("%d %d %d", &n1, &n2, &m); //инициализируем список смежности размерности n1 adj = new vector[n1];

//считываем граф, заданный списком ребер
for (int i = 0; i < m; ++i) { int v, w; scanf("%d %d", &v, &w); v--; w--; //добавляем ребро (v, w) в граф adj[v].push_back(w); } used.assign(n1, false); mt.assign(n2, -1); } void solve() { //находим максимальное паросочетание for (int v = 0; v < n1; ++v) { used.assign(n1, false); //если нашли увеличивающую цепь, //то размер максимального паросочетания увеличиваем на 1 if (kuhn(v)) { mtSize++; } } } void printData() { printf("%d\n", mtSize); for (int i = 0; i < n2; ++i) { if (mt[i] != -1) { printf("%d %d\n", mt[i] + 1, i + 1); } } } int main() { readData(); solve(); printData(); return 0; }

 

Пример
Входные данные
5 4 8
1 1
2 1
3 1
3 2
4 2
4 3
5 3
5 4
Выходные данные
4
1 1
2 2
4 3
5 4

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++