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

Java   28 сентября 2015  Автор статьи:  
geekbrains.ru/

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


private ArrayList 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). Далее выводятся ребра этого максимального паросочетания, заданные парами вершин. Первая вершина ребра является вершиной первой доли, вторая вершина ребра — вершиной второй доли соответственно.


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 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();
}

//считываем граф, заданный списком ребер
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++

geekbrains.ru/
geekbrains.ru/