二分图的最大匹配
程序员文章站
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);
}
}
参考
《啊哈!算法》