二分图的最大匹配——《啊哈！算法》

本文主要是介绍二分图的最大匹配——《啊哈！算法》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二分图

如果一个图的所有顶点可以被分为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;@Overridepublic 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];}@Overridepublic 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;}@Overridepublic 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);}}