详解二分图判断与最大匹配

本文旨在给出二分图（bipartite graph）判断与最大匹配的标准算法模板，以供自己日后使用。

首先给出二分图的定义：

如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图

可以证明，二分图的充要条件为所有的环路（cycles）都具有偶数条边构成。

Two-colorable Algorithm Template

判断二分图的方法正是从定义中来：使用两种颜色给输入图的每个顶点染色，并且让任意相邻顶点的染色不同，如果可以进行染色，那么就证明了输入图是二分图。

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<bool> marked(n, false);
        vector<int> colors(n, 0);

        for (int i = 0; i < n; ++i) {
            int expected = (colors[i] != 0) ? colors[i] : 1;
            if (!dfs(graph, i, marked, colors, expected)) {
                return false;
            }
        }
        return true;
    }

    bool dfs(const vector<vector<int>> &graph, int i, vector<bool> &marked, vector<int> &colors, int expected) {
        if (!marked[i]) {
            marked[i] = true;
            colors[i] = expected;
            for (const int adj : graph[i]) {
                if (!dfs(graph, adj, marked, colors, -expected)) {
                    // fail as soon as possible
                    return false;
                }
            }
        } 
        return colors[i] == expected;
    }
};

Hungarian Algorithm Template

对于二分图的最大匹配问题（maximum cardinality matching），描述如下：

对于给定的二分图，选择尽可能多的边，在这些已选择的边中，没有任何两个边共享同一个顶点

在正式介绍最大匹配算法（匈牙利算法，又称KM算法）前，首先先明确以下概念：

• 匹配（matching）: 成对的不相邻边的集合（也就是说，对于图中的任何一个顶点，匹配集合中最多有一条边与之关联）
• 最大匹配（maximum matching）：在给定的图中，所有可能的匹配中基数（cardinality）最大的匹配
• 饱和（saturation）：在给定图中，所有那些与匹配（matching）有边相连的顶点（度数为1）
• 路径/简单路径（path）：长度为k的路径/简单路径指的是包含k条边，这些边相互连接形成一条路径
• 交错路径（alternating path）：在给定图中，路径上的边交替地属于/不属于匹配（matching）
• 增广路径（augmenting path）：起始点和终止点（路径两端的顶点）不饱和的交错路径

可以证明，\(M\)是最大匹配的充要条件是对于当前的匹配\(M\)，不存在增广路径。形象的理解就是，如果对于当前的匹配\(M\)存在增广路径，并且假设此时匹配的边数为n，那么整个增广路径（2n + 1）就有n条边在匹配集合中，有n + 1条边不在匹配集合中，此时我们将匹配变换为这n + 1条边，就可以得到一个更大的匹配。

增广路径上的起始点和终止点，一定是分别属于二分图的一侧和另一侧。

现在有N个病人（patient），每个病人可选两个doctor（A，B）中的一个作为自己的私人医生，医生总数为S，且同一个医生最多服务一个病人。给定数组A，B，其中A[i]表示病人i可选的doctorA，B[i]表示病人i可选的doctorB，问是否存在匹配使得所有的病人都能有自己的医生？

DFS版本的匈牙利算法模板如下：

class Solution {
   private:
    static const int INVALID = -1;

   public:
    bool matchPatientWithDoctor(vector<int> &A, vector<int> &B, int S) {
        int N = A.size();
        if (N > S) return false;

        vector<vector<int>> graph(N);
        for (int p = 0; p < N; ++p) {
            graph[p].emplace_back(A[p] - 1);
            graph[p].emplace_back(B[p] - 1);
        }

        vector<int> l_match(N, INVALID);
        vector<int> r_match(S, INVALID);
        vector<bool> marked(N, false);

        for (int p = 0; p < N; ++p) {
            // 当把二分图中一侧的顶点全部扫描完成后，当前的匹配即为最大匹配
            if (!canMatch(graph, p, marked, l_match, r_match)) {
                return false;
            }
        }
        return true;
    }

    bool canMatch(const vector<vector<int>> &graph, int p, vector<bool> &marked, vector<int> &l_match, vector<int> &r_match) {
        // 对于起始左侧顶点p，外加一层判断，若失败则进入DFS
        if (l_match[p] != INVALID) return true;
        // 关键！这里的marked不是为了避免环路，而是在一个顶点上找不到增广路径时，没有必要再去它的所有子图中找增广路径了
        // 所以每次进行DFS前都要将marked重置为false
        fill(marked.begin(), marked.end(), false);
        return dfs(graph, p, marked, l_match, r_match);
    }

    // 每次的DFS调用，都可以保证p是病人集合（左侧）的顶点
    // DFS返回值为是否找到了一条增广路径（即最初的顶点是否可以加入匹配中）
    bool dfs(const vector<vector<int>> &graph, int p, vector<bool> &marked, vector<int> &l_match, vector<int> &r_match) {
        marked[p] = true;
        // 这里的for-loop是在遍历交错路径上不属于当前匹配的边

        // 启发式算法，优先找直接能匹配的右侧顶点（增广路径len = 1），实在没有的时候再去找普通的增广路径
        for (const int d : graph[p]) {
            if (r_match[d] == INVALID) {
                l_match[p] = d;
                r_match[d] = p;
                return true;
            }
        }

        for (const int d : graph[p]) {
            if (!marked[r_match[d]] && dfs(graph, r_match[d], marked, l_match, r_match)) {
                l_match[p] = d;
                r_match[d] = p;
                return true;
            }
        }
        // 这里千万不能在返回前将marked[p]重置为false，否则将会变成路径回溯，找出全部可能的路径（在无效的顶点上找增广路径），
      	// 路径回溯算法在给定图的时间复杂度是超过多项式时间的，如果是完全图，则时间复杂度约为O(N!)
        // 应该在每次DFS开始时进行marked数组的重置
        return false;
    }
};

一次DFS算法的时间复杂度是\(O(N)\)；

对于左侧集合的顶点，每一个顶点都尝试一次DFS加入匹配，因此整个匈牙利算法的时间复杂度是\(O(N^2)\)

Kuhn-Munkres Algorithm Template

对于每个边有权重的图，我们在进行最大匹配的时候要考虑到边加权值，即获得边的加权值总和最大的匹配（maximum weight matching）。

对于含有权重边的匹配问题，需要用到Kuhn-Munkres算法，首先先明确以下概念：

• 完美匹配（perfect matching）: 给定图中的所有顶点都与匹配\(M\)中的某一条边相关联（adjacent to）

• 顶标（labeling）: 给定图中的任意一个顶点\(v\)，都有一个值\(l(v)\)

• 可行顶标（feasible labeling）：\(l(x) + l(y) >= weight(x, y), \forall x \in X, y \in Y\)，其中\(X\)是左侧顶点集，\(Y\)是右侧顶点集

• 相等子图（equality graph）：对于原始给定图\(G = (V, E)\)，它的相等子图为\(G_l = (V, E_l)\)。相等子图\(G_l\)包含图\(G\)的所有顶点，但只包含边的权重等于两端顶标和的那些边：\(E_l = (x, y): l(x) + l(y) = weight(x, y)\)

有以下KM定理成立：

如果\(l\)是可行顶标，\(M\)是相等子图\(G_l\)里的完美匹配，那么\(M\)就是图\(G\)的最大权匹配。而且此时\(M\)的边权重和为原图\(G\)的所有顶标和

KM定理将求解最大权匹配的问题转化成了求完美匹配的问题

因为我们要找完美匹配，所以需要首先保证二分图两个顶点集的顶点数量相同：将两个顶点集中顶点数少的补点，使得两边顶点数相同；同时为了确保可行顶标，将所有不存在的边权重一律设为0。

整个算法描述如下：

1. 给定初始可行顶标\(l\)和初始匹配\(M\)
2. 当\(M\)不是\(E_l\)的完美匹配时，重复以下操作：
   1. 在相等子图\(E_l\)中寻找增广路径，然后通过修改匹配使得匹配数 + 1
   2. 如果找不到增广路径，那么将可行顶标\(l\)改进为\(l'\)使得\(E_l \subset E_{l'}\)
3. 重复步骤2，直到找到完美匹配

最大权匹配的算法模板可以参见OI Wiki或者Algorithm，我个人暂时尚不能完全理解，不做过多介绍。

Bipartite Property

在二分图中，以下的概念和最大匹配问题紧密相关：

最小点覆盖（minimum vertex cover）：二分图中的最小点覆盖的顶点数（也就是集合基数cardinality）= 最大匹配的边数

点覆盖（vertex cover）：顶点的集合，使得图中任何一条边都至少有一个端点（endpoint）在集合中

最大独立集（maximum independent set）：二分图中的最大独立集的顶点数 = 总顶点数 - 最小点覆盖的顶点数

独立集（independent set）：顶点的集合，集合中任意两个顶点不相邻（no adjacent，没有一条边相连）

最大独立集是最小点覆盖的补集（complement）

References

• [CP Algorithms] Check whether a graph is bipartite
• [CP Algorithms] Kuhn's Algorithm for Maximum Bipartite Matching
• Kuhn-Munkres 算法
• [OI Wiki] 二分图最大匹配
• [OI Wiki] 二分图最大权匹配
• [Princeton] Algorithm 4th related codes
• Leetcode 785
• Leetcode 886
• UOJ 78 二分图最大匹配
• UOJ 80 二分图最大权匹配