二分图匹配和匈牙利算法

内容概要：

最大流算法解决二分图最大匹配
匈牙利算法
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;
    }
}