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

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

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

1
2
3
4
vector<int> *adj; //список смежности
vector<bool> used; //массив для хранения информации о пройденных и не пройденных вершинах
int mtSize = 0; //размер максимального паросочетания
vector<int> 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). Далее выводятся ребра этого максимального паросочетания, заданные парами вершин. Первая вершина в паре является вершиной первой доли, вторая вершина — вершиной второй доли соответственно.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <vector>

using namespace std;

int n1; //количество вершин в первой доле графа
int n2; //количество вершин во второй доле графа
int m; //количество ребер в графе
vector<int> *adj; //список смежности
vector<bool> used; //массив для хранения информации о пройденных и не пройденных вершинах
int mtSize = 0; //размер максимального паросочетания
vector<int> 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<int>[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++