最大匹配与完全匹配
下面我们讲解的算法都是有关于二分图的算法
例如对于上图就是一个二分图，每条边都连接了两个不同部分的节点，生活中很多问题都可以建模为二分图的问题，例如相亲。左边表示男生群体，右边表示女生群体，如果两个节点之间有一条边，说明这一对男女可以匹配为一对；另外又比如求职，左边的节点表示求职者，右边的节点表示公司，如果节点之间有一条边，表明求职者与公司互相都比较满意，可以匹配。
现在我们关心的问题是，向这样的二分图最多有多少个匹配，这样的问题称为最大匹配问题，如果最大匹配的个数与左右两边的节点数目都相同，那么就称为是完全匹配，对于相亲来说，意味着每一个人都可以找到另一半，对于求职来说，每个求职者都可以找到一家公司。
最大流解决匹配问题
解决最大匹配问题的一个方案就是将上面的图建模为一个网络流
图中的每一条边的权值都为 1，即每条边的允许通过的最大流量为 1，表示每一个节点都只能被匹配一次，此时这个网络流的最大流就等于最大匹配数，我们将求二分图的最大匹配问题转化为了求网络流的最大流问题，而求最大流的问题我们在以前已经接触过。
我们唯一需要的工作量就是根据上面的二分图得到一个网络流的模型，具体见代码
public class BipartiteMatching {
private Graph graph;
private int maxMatching;
public BipartiteMatching(Graph graph) {
this.graph = graph;
BinaryPartitionDetection bpd = new BinaryPartitionDetection(graph);
if (!bpd.isBipartite()) {
throw new IllegalArgumentException("该图不为一个二分图");
}
int[] colors = bpd.colors();
DirectedWeightedGraph directedWeightedGraph = new DirectedWeightedGraph(graph.V() + 2);
for (int v = 0; v < graph.V(); v++) {
if (colors[v] == 0) {
directedWeightedGraph.addEdge(graph.V(), v, 1);
} else {
directedWeightedGraph.addEdge(v, graph.V() + 1, 1);
}
for (int w: graph.adj(v)) {
if (v < w) {
if (colors[v] == 0) {
directedWeightedGraph.addEdge(v, w, 1);
} else {
directedWeightedGraph.addEdge(w, v, 1);
}
}
}
}
MaxFlow maxFlow = new MaxFlow(directedWeightedGraph, graph.V(), graph.V() +1);
maxMatching = maxFlow.result();
}
public int result() {
return maxMatching;
}
public boolean isPerfectMatching() {
return maxMatching * 2 == graph.V();
}
}
|
上面对二分图检测以及最大流的类在之前文章讲解过，不多加介绍。
LCP04 覆盖是一道 LeetCode 上的题目，我们可以将这道题建模为二分图的最大匹配问题。
题目介绍
你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为 $1 * 2$ 的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌? 这些骨牌可以横着或者竖着放。
解题思路
对于棋盘问题，如果玩过国际象棋的话，就知道棋盘是被染为黑白两色的，如
同理我们也可以将上面的棋盘根据上面的染色分为两个区域，如果将网格上的一个个网格看做是图中的节点的话，这不就是一个二分图吗? 而对一个 $1 * 2$ 的多米诺骨牌，它总是一边在黑色区域，一边在白色区域，题目问能够放置多少块多米诺骨牌不就是在问该二分图的最大匹配图吗?
因为我们成功的将上面的问题建模为了二分图的最大匹配，可以利用我们上面的算法进行解决，现在唯一的难点可能就是将上面的网格建模为一个图了，代码如下
import java.util.*;
public class Solution {
public int domino(int n, int m, int[][] broken) {
int[][] board = new int[n][m];
for (int[] p: broken) {
board[p[0]][p[1]] = 1;
}
AdjSet graph = new AdjSet(n * m);
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) {
graph.addEdge(i * m + j, i * m + j + 1);
}
if (i + 1 < n && board[i][j] == 0 && board[i + 1][j] == 0) {
graph.addEdge(i * m + j, (i + 1) * m + j);
}
}
}
BipartiteMatching bm = new BipartiteMatching(graph);
return bm.result();
}
}
|
匈牙利算法
解决匹配问题的另一个算法就是匈牙利算法，还是以下图为例
匈牙利算法的思想就是每次从左边未匹配的点出发进行遍历，如果右边的点没有匹配，则将它们匹配为一对
上面我们从节点 0 出发，来到节点 4，发现节点 4 没有被匹配，因此将它们设置为匹配，我们使用一个数组来进行记录
matching[0] = 4;
matching[4] = 0;
|
如果右边的节点已经被遍历了，则从右边节点匹配的节点继续遍历，例如对于下图，我们从 1 出发，来到节点 4，发现节点 4 已经被遍历了，于是来与节点 4 匹配的节点 0，然后从 0 开始向右遍历，直到向右找到一个未匹配的节点
上面我们遍历的路径是 $1 → 4 → 0 → 6$，本来 0-4 是匹配的，现在我们让它断开，让 1-4、0-6 匹配。
重复上面的过程，每次如果在右边找到一个未匹配的节点，匹配数加一，当我们遍历完左边所有的未匹配的节点时，最终的匹配数就是最大匹配数，这就是匈牙利算法。
这里总结一下匈牙利算法的流程：
- 从左边未匹配的节点遍历，如果右边的节点未匹配，那么让二者匹配，匹配数加一
- 否则右边的节点已匹配，那么从右边节点匹配的节点继续遍历
- 重复上面的过程，直到找到一个右边未匹配的节点，那么匹配数加一，并且更新匹配关系
根据遍历的顺序不同，匈牙利算法有两种实现，一种是使用 BFS 进行遍历，该种方法速度较快，但是代码复杂
import java.util.*;
public class HungarianBFS {
private Graph graph;
private int[] matching;
private int maxMatching;
public HungarianBFS(Graph graph) {
this.graph = graph;
BinaryPartitionDetection bpm = new BinaryPartitionDetection(graph);
if (!bpm.isBipartite()) {
throw new IllegalArgumentException("该图不是二分图");
}
this.matching = new int[graph.V()];
Arrays.fill(matching, -1);
int[] colors = bpm.colors();
for (int v = 0; v < graph.V(); v++) {
if (colors[v] == 0 && matching[v] == -1) {
if (bfs(v)) {
maxMatching++;
}
}
}
}
private boolean bfs(int v) {
Queue<Integer> queue = new LinkedList<>();
queue.add(v);
int[] pre = new int[graph.V()];
Arrays.fill(pre, -1);
pre[v] = v;
while (!queue.isEmpty()) {
int cur = queue.remove();
for (int next: graph.adj(cur)) {
if (pre[next] == -1) {
if (matching[next] != -1) {
queue.add(matching[next]);
pre[next] = cur;
pre[matching[next]] = next;
} else {
pre[next] = cur;
ArrayList<Integer> path = getPath(pre, v, next);
for (int i = 0; i < path.size(); i += 2) {
matching[path.get(i)] = path.get(i + 1);
matching[path.get(i + 1)] = path.get(i);
}
return true;
}
}
}
}
return false;
}
private ArrayList<Integer> getPath(int[] pre, int start, int end) {
int cur = end;
ArrayList<Integer> result = new ArrayList<>();
while (cur != start) {
result.add(cur);
cur = pre[cur];
}
result.add(start);
Collections.reverse(result);
return result;
}
public int result() {
return maxMatching;
}
}
|
还有一种实现是使用 DFS 进行遍历，虽然比 BFS 慢一丢丢，但还是实现简单
import java.util.Arrays;
public class HungarianDFS {
private Graph graph;
private int maxMatching;
private boolean[] visited;
private int[] matching;
public HungarianDFS(Graph graph) {
this.graph = graph;
BinaryPartitionDetection bmp = new BinaryPartitionDetection(graph);
if (!bmp.isBipartite()) {
throw new IllegalArgumentException("该图不是二分图");
}
int[] colors = bmp.colors();
this.maxMatching = 0;
this.visited = new boolean[graph.V()];
this.matching = new int[graph.V()];
Arrays.fill(matching, -1);
for (int v = 0; v < graph.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 w: graph.adj(v)) {
if (!visited[w]) {
visited[w] = true;
if (matching[w] == -1 || dfs(matching[w])) {
matching[v] = w;
matching[w] = v;
return true;
}
}
}
return false;
}
public int result() {
return maxMatching;
}
}
|
同理我们可以使用匈牙利算法来完成上面的 LeetCode 问题
import java.util.*;
public class Solution {
public int domino(int n, int m, int[][] broken) {
int[][] board = new int[n][m];
for (int[] p: broken) {
board[p[0]][p[1]] = 1;
}
AdjSet graph = new AdjSet(n * m);
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) {
graph.addEdge(i * m + j, i * m + j + 1);
}
if (i + 1 < n && board[i][j] == 0 && board[i + 1][j] == 0) {
graph.addEdge(i * m + j, (i + 1) * m + j);
}
}
}
HungarianBFS hungarianBFS = new HungarianBFS(graph);
return hungarianBFS.result();
}
}
|
速度比使用网络流要快
微信
支付宝
