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

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

Java

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

Статья
Комментарии (0)

Задан неориентированный двудольный граф $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++

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

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

на Delphi

на Java

на C++