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

Java   28 Сентябрь 2015  Автор статьи:  

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

1
2
3
4
private ArrayList<Integer> adj[]; //список смежности
private boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах
int mtSize = 0; //размер максимального паросочетания
private 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Kuhn {
   
    private int n1; //количество вершин в первой доле графа
    private int n2; //количество вершин во второй доле графа
    private int m; //количество ребер в графе
    private ArrayList<Integer> adj[]; //список смежности
    private boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах
    int mtSize = 0; //размер максимального паросочетания
    private int mt[]; //массив для хранения ребер, образующих максимальное паросочетание
   
    private BufferedReader cin;
    private PrintWriter cout;
    private StringTokenizer tokenizer;
   
    //алгоритм Куна поиска максимального паросочетания
    private boolean kuhn(int v) {
        //если вершина является пройденной, то не производим из нее вызов процедуры
        if (used[v]) {
            return false;
        }
        used[v] = true; //помечаем вершину первой доли, как пройденную
        //просматриваем все вершины второй доли, смежные с рассматриваемой вершиной первой доли  
        for (int i = 0; i < adj[v].size(); ++i) {
            int w = adj[v].get(i);
            //нашли увеличивающую цепь, добавляем ребро (v, w) в паросочетание
            if (mt[w] == -1 || kuhn(mt[w])) {
                mt[w] = v;
                return true;
            }
        }
        return false;
    }  
   
    //процедура считывания входных данных с консоли
    private void readData() throws IOException {
        cin = new BufferedReader(new InputStreamReader(System.in));
        cout = new PrintWriter(System.out);
        tokenizer = new StringTokenizer(cin.readLine());
       
        n1 = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа в первой доли графа
        n2 = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа во второй доли графа
        m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа
       
        //инициализируем список смежности графа размерности n
        adj = new ArrayList[n1];
        for (int i = 0; i < n1; ++i) {
            adj[i] = new ArrayList<Integer>();
        }
       
        //считываем граф, заданный списком ребер
        for (int i = 0; i < m; ++i) {
            tokenizer = new StringTokenizer(cin.readLine());
            int v = Integer.parseInt(tokenizer.nextToken());
            int w = Integer.parseInt(tokenizer.nextToken());
            v--;
            w--;
            adj[v].add(w); //добавляем ребро (v, w) в граф
        }
       
        used = new boolean[n1];
        Arrays.fill(used, false);
        mt = new int[n2];
        Arrays.fill(mt, -1);
    }
   
    private void solve() {
        //находим максимальное паросочетание
        for (int v = 0; v < n1; ++v) {
            Arrays.fill(used, false);
            //если нашли увеличивающую цепь,
            //то размер максимального паросочетания увеличиваем на 1
            if (kuhn(v)) {
                mtSize++;
            }
        }
    }
   
    //процедура вывода данных в консоль
    private void printData() throws IOException {
        cout.println(mtSize);
        for (int i = 0; i < n2; ++i) {
            if (mt[i] != -1) {
                cout.println((mt[i] + 1) + " " + (i + 1));
            }
        }
        cout.println();
    }
   
    private void run() throws IOException {
        readData();
        solve();
        printData();
       
        cin.close();
        cout.close();
    }
   
    public static void main(String[] args) throws IOException {
        Kuhn solution = new Kuhn();
        solution.run();
    }
}

 

Пример
Входные данные
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++