欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分图的最大匹配

程序员文章站 2024-03-16 23:44:28
...

二分图

如果一个图的所有顶点可以被分为X和Y两个集合,并且所有边的两个顶点恰好一个属于X,另外一个属于Y,即每个集合内的顶点没有边相连,那么此图就是二分图。

二分图在任务调度、工作安排等方面有较多的应用。

判断二分图:首先将任意一个顶点着红色,然后将其相邻的顶点着蓝色,如果按照这样的着色方法可以将全部顶点着色的话,并且相邻的顶点着色不同,那么该图就是二分图。

二分图的最大匹配

java代码

package com.hyl.algorithm.other;

import java.util.Arrays;

import com.hyl.algorithm.search.base.SearchIntf;
import com.hyl.algorithm.search.base.SearchIntfFactory;

/**
 * 二分图最大匹配
 * <p>
 *
 * @author Hyl
 * @version V 0.1
 * @since 0.1 2020-07-01 13:22
 */
public class MaxMatch implements SearchIntf {

    private LinkedGraph graph;

    private int n, m, count;

    private int[] boy, girl;

    @Override
    public void init() {
        n = 3;
        m = 5;
        graph = new LinkedGraph(n, m);
        graph.addDirected(1, 1, 1);
        graph.addDirected(1, 2, 1);
        graph.addDirected(2, 2, 1);
        graph.addDirected(2, 3, 1);
        graph.addDirected(3, 1, 1);

        boy = new int[n + 1];
        girl = new int[n + 1];
    }

    @Override
    public void find() {
        Arrays.fill(girl, 0);
        for (int i = 1; i <= n; i++) {
            findGirlMatchBoy(i);
        }
    }

    private void findGirlMatchBoy(int girl) {
        Arrays.fill(boy, 0);
        if (dfs(girl)) {
            count++;
        }
    }

    private boolean dfs(int u) {
        int index = graph.first[u];

        while (index != -1) {

            if (boy[graph.v[index]] == 0) {
                boy[graph.v[index]] = 1;

                if (girl[graph.v[index]] == 0 || dfs(girl[graph.v[index]])) {
                    girl[graph.v[index]] = u;
                    return true;
                }
            }

            index = graph.next[index];
        }

        return false;
    }

    @Override
    public void print() {
        graph.printLines();
        System.out.println("最大匹配:" + count);
        System.out.println(Arrays.toString(boy));
        System.out.println(Arrays.toString(girl));
    }

    public static void main(String[] args) {
        SearchIntfFactory.produce(MaxMatch.class);
    }

}

参考

《啊哈!算法》

相关标签: 回读