二分图匹配和匈牙利算法
内容概要：
- 最大流算法解决二分图最大匹配
- 匈牙利算法
- LeetCode上一个困难问题：覆盖
匹配问题相关概念
该类问题的前提是图为二分图。关于二分图包括二分图检测在前面的文章已经讨论过了。
匹配：给定一个二分图G，在G的一个子图M中， M的边集{E}中的任意两条边都不交汇于同一个结点，则称M是一个匹配(Matching)。 简言之，在关注边的情况下，二分图G的一个匹配就是满足任意两条边之间都没有公共顶点的边的子集。
极大匹配：极大匹配(Maximal Matching)是指在当前已完成的匹配下，无法再通过增加未完成匹配的边的方式来增加匹配的边数。
最大匹配：最大匹配(Maximum Matching)是所有极大匹配当中边数最多的一个匹配。
完全匹配：如果二分图G的一个匹配中，图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配(Perfect Matching)，也称作完备匹配。
最大流算法解决最大匹配问题
算法思路
最大匹配问题可以用最大流算法解决，关于最大流问题，在上篇文章已经讨论过了，最大流问题和Edmonds-Karp算法。
最大流解决匹配问题的思路是这样的，首先建立一张新图：
构建图
该图在原图的基础上，增加一个源点s和汇点t，原二分图G的两部分分别连接s和t，方向如上图所示，每个边上的容量均为1，该图的最大流就是原二分图G的最大匹配数。这是因为源点发出的边的数目为二分图左侧顶点数，汇点的入边数为二分图右侧顶点数，由于每个边容量为1，在流量平衡限制下，源点进入左侧每个顶点的流量最多为1，左侧每个顶点进入右侧顶点流量最多为1，每个右侧顶点进入汇点的流量最多为1，这就意味着二分图G左侧的每个顶点最多和右侧的一个匹配上，没有匹配的不会构成可行流。
算法实现
public class BipartiteMatching {
private Graph G;
private int maxMatching;
public BipartiteMatching(Graph G){
BipartitionDetection bd = new BipartitionDetection(G);
if(!bd.isBipartite())
throw new IllegalArgumentException("Only Works On BipartitionGraph!");
this.G = G;
int []colors = bd.colors();
// 源点编号 V， 汇点编号 V + 1
WeightedGraph network = new WeightedGraph(G.V() + 2, true);
for(int v = 0; v < G.V(); v ++){
if(colors[v] == 0)// 颜色为0设为左侧顶点
network.addEdge(G.V(), v, 1);
else network.addEdge(v, G.V() + 1, 1);
for(int w: G.adj(v))
if(v < w) { // 这样方向不同的边只遍历一次
if(colors[v] == 0) network.addEdge(v, w, 1);
else network.addEdge(w, v, 1);
}
}
MaxFlow mf = new MaxFlow(network, G.V(), G.V() + 1);
maxMatching = mf.result();
}
public int maxMatching(){
return maxMatching;
}
public static void main(String args[]){
Graph g = new Graph("g.txt", false);
BipartiteMatching bm = new BipartiteMatching(g);
System.out.println(bm.maxMatching());
}
}
匈牙利算法
匈牙利算法是另一个求解最大匹配的算法，它比使用最大流算法解决最大匹配效率要高，而且该算法的思想非常简单。
算法描述
从左侧的非匹配点出发，如果来到的右边点是一个匹配过的点，从右向左走只能走匹配过的边，这样走过的路径一定是匹配边和未匹配边交替出现的路径。如果上述过程最终终止于另外一个未匹配点(这个点只可能在右侧)，此时称找到的路径为增广路径。
增广路径一定是包含偶数个顶点，奇数条边的路径，且起点和终点一定是未匹配状态。这样将匹配边和未匹配边互换就能多出一个匹配来，且原来匹配状态的点一定还是匹配状态，而多出的两个匹配点就是起点和终点。
匈牙利算法1
执行匈牙利算法，首先可以得到0-4一个匹配；接着左侧顶点1未匹配，从顶点1走到顶点4，顶点4已经是匹配状态，沿匹配边回到0，然后0走到6，本轮寻找终止，路径为1-4-0-6，这样得到1-4和0-6为匹配。(当然也可以走路径1-7，可以直接得到一个新的匹配，这里选1-4-0-6是为了讲述匈牙利算法的中间过程。)接着左侧顶点2未匹配，从顶点2走到顶点6，顶点6已经是匹配状态，沿匹配边回到0，然后0走到4，4沿匹配边回到1，1走到7，本轮寻找终止，路径为2-6-0-4-1-7，这样得到2-6、0-4、1-7为匹配。
匈牙利算法2
接着左侧顶点3未匹配，从顶点3走到顶点5，直接得到一个新的匹配，最大匹配寻找完成。(如果从顶点3走到顶点7，顶点7回到顶点1，顶点1走到4，4回到0，0走到6，6回到2，本轮寻找终止，路径为3-7-1-4-0-6-2，不是增广路径，不会有新的匹配产生。最终还是走3-5。)
算法实现(BFS实现)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Hungarian {
private Graph G;
private int maxMatching = 0;
private int[] matching;// 记录匹配状态，-1 表示未匹配
public Hungarian(Graph G){
BipartitionDetection bd = new BipartitionDetection(G);
if(!bd.isBipartite())
throw new IllegalArgumentException("Only Works On BipartitionGraph!");
this.G = G;
int []colors = bd.colors();
matching = new int[G.V()];
Arrays.fill(matching, -1);
for(int v = 0; v < G.V(); v ++)
if(colors[v] == 0 && matching[v] == -1) // 左侧的点
if(bfs(v)) maxMatching ++;
}
private boolean bfs(int v){
Queue<Integer> q = new LinkedList<>();
int pre[] = new int[G.V()];
Arrays.fill(pre, -1);
q.add(v);
pre[v] = v;
while(!q.isEmpty()){
int cur = q.remove();
for(int next: G.adj(cur))
if(pre[next] == -1){
if(matching[next] != -1){
pre[next] = cur;
pre[matching[next]] = next;
q.add(matching[next]);
}else {
pre[next] = cur;
ArrayList<Integer> augPath = getAugPath(pre, v, next);
// 匹配边变换
for (int i = 0; i < augPath.size(); i += 2) {
matching[augPath.get(i)] = augPath.get(i + 1);
matching[augPath.get(i+1)] = augPath.get(i);
}
return true;
}
}
}
return false;
}
private ArrayList<Integer> getAugPath(int[]pre, int start, int end){
ArrayList<Integer> res = new ArrayList<>();
int cur = end;
while(cur != start){
res.add(cur);
cur = pre[cur];
}
res.add(cur);// 逆序没关系
return res;
}
public int maxMatching(){
return maxMatching;
}
public boolean isPerfectMacthing(){
return maxMatching * 2 == G.V();
}
public static void main(String args[]){
Graph g = new Graph("g.txt", false);
Hungarian hg = new Hungarian(g);
System.out.println(hg.maxMatching());
}
}
当然匈牙利算法也可以用DFS来实现增广路径的寻找，由于使用了递归，代码会比BFS实现的要简洁。
import java.util.ArrayList;
import java.util.Arrays;
public class HungarianDFS {
private Graph G;
private int maxMatching = 0;
private boolean[] visited;
private int[] matching;// 记录匹配状态，-1 表示未匹配
public HungarianDFS(Graph G){
BipartitionDetection bd = new BipartitionDetection(G);
if(!bd.isBipartite())
throw new IllegalArgumentException("Only Works On BipartitionGraph!");
this.G = G;
int []colors = bd.colors();
matching = new int[G.V()];
Arrays.fill(matching, -1);
visited = new boolean[G.V()];
for(int v = 0; v < G.V(); v ++)
if(colors[v] == 0 && matching[v] == -1) { // 左侧的点
Arrays.fill(visited, false);
if (dfs(v)) maxMatching++;
}
}
private boolean dfs(int v){
visited[v] = true;
for(int u: G.adj(v))
if(!visited[u]){
visited[u] = true;
if(matching[u] == -1 || dfs(matching[u])){
matching[v] = u;
matching[u] = v;
return true;
}
}
return false;
}
public int maxMatching(){
return maxMatching;
}
public boolean isPerfectMacthing(){
return maxMatching * 2 == G.V();
}
public static void main(String args[]){
Graph g = new Graph("g.txt", false);
HungarianDFS hg = new HungarianDFS(g);
System.out.println(hg.maxMatching());
}
}
最大匹配的一个应用实例：覆盖
LCP4
例子
问题分析
如果将棋盘格按照黑白进行染色，相邻的格子不同色，则一个多米诺骨牌必然占据相邻的一个白格子和一个黑格子。这样就可以把问题看做一个二分图的最大匹配，黑白分别对应二分图的两部分。在问题所抽象到的二分图中，每个格子是一个顶点，每个顶点和其上下左右的四个顶点相连。
问题解答
将问题抽象出的图的邻接集合建立出来，然后使用匈牙利算法求最大匹配。
class Solution {
TreeSet<Integer> g[];// 用于构建图
int colors[]; // 图 g 二分后的各个顶点颜色 0 或者 1
boolean visited[];
int matching[]; // 已经匹配的
int maxMatch = 0; // 最大匹配数
public int domino(int n, int m, int[][] broken) {
int[][] board = new int[n][m];
g = new TreeSet[m*n];
colors = new int[m*n];
Arrays.fill(colors, -1); // 没有被染色
visited = new boolean[m*n];
matching = new int[m*n];
Arrays.fill(matching, -1);
for(int i = 0; i < m * n; i ++)
g[i] = new TreeSet<>();
for(int[] p: broken) board[p[0]][p[1]] = 1; // 为 1 表示不可放骨牌，为 0 可以
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++){
if(j + 1 < m && board[i][j] == 0 && board[i][j+1] == 0) {
g[i * m + j].add(i * m + j + 1);
g[i * m + j + 1].add(i * m + j);
}
if(i + 1 < n && board[i][j] == 0 && board[i+1][j] == 0) {
g[i * m + j].add((i + 1) * m + j);
g[(i + 1) * m + j].add(i * m + j);
}
}
for(int v = 0; v < m * n; v ++)
if(!visited[v])
dfs(v, 0);
for(int v = 0; v < m*n; v ++)
if(colors[v] == 0 && matching[v] == -1) { // 左侧的点
Arrays.fill(visited, false);
if (Hungar(v)) maxMatch ++;
}
return maxMatch;
}
private void dfs(int v, int color){
// 预处理出colors数组,即二分图的两个部分
colors[v] = color;
visited[v] = true;
for(int w: g[v]){
if(!visited[w]) dfs(w, 1 - color);
}
}
private boolean Hungar(int v){
visited[v] = true;
for(int u: g[v])
if(!visited[u]){
visited[u] = true;
if(matching[u] == -1 || Hungar(matching[u])){
matching[v] = u;
matching[u] = v;
return true;
}
}
return false;
}
}
