Алгоритм поиска максимального паросочетания в двудольном графе (реализация на Java)
Задан неориентированный двудольный граф , имеющий
вершин в первой доли,
вершин во второй доли и
ребер. Требуется найти в нем максимальное паросочетание (множество попарно несмежных рёбер, то есть рёбер, не имеющих общих вершин наибольшей мощности).
Исходный двудольный граф удобно представлять в памяти ЭВМ списком смежности
, храня для каждой вершины первой доли
список
смежных с ней вершин второй доли. Булевский массив
служит для отметки о том, стала вершина графа
пройденной в процессе работы алгоритма или еще нет. При этом, если
, то вершина
является пройденной, если
, то нет.
private ArrayList
private boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах
int mtSize = 0; //размер максимального паросочетания
private int mt[]; //массив для хранения ребер, образующих максимальное паросочетание
В качестве списка смежности для представления графа на языке C++ удобно использовать массив, каждый элемент которого является структурой данных .
В приведенной ниже реализации данные считываются и выводятся в консоль.
В первой строке входного файла задано три целых числа: – количество вершин в первой доли графа,
– количество вершин во второй доли графа и
– количество ребер графа соответственно. Каждая из следующих
строк содержит описание ребра графа парами вершин: первое число — вершина первой доли, второй число — вершина второй доли. Первое число находятся в диапазоне от
до
, второе число – в диапазоне от
до
.
В первой строке выходного файла показано количество ребер в некотором максимальном паросочетании исходного двудольного графа . Далее выводятся ребра этого максимального паросочетания, заданные парами вершин. Первая вершина ребра является вершиной первой доли, вторая вершина ребра — вершиной второй доли соответственно.
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
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
}
//считываем граф, заданный списком ребер
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 |