匈牙利算法

发表于 更新于 分类于 Waline：

接触到这个算法是因为看到了一个题目，叫做素数伴侣。就是说给你你串数字，从中选择两个数字相加，如果他们的和是个素数，那么这一对叫做素数伴侣。然后我们需要找到这串数字中最多能找到多少对素数伴侣。

这个问题的解法首先是把数字分为两部分，一部分是偶数，一部分是奇数，因为两个偶数相加或者两个奇数相加一定还是偶数，不可能是素数。

于是这个问题就变成了分别从偶数中选一个，然后从奇数中选一个，看看最多选出多少对相加为素数。这个问题就用到了匈牙利算法。

匈牙利算法主要用于解决一些与二分图匹配有关的问题，所以我们先来了解一下二分图。

二分图

二分图：又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边所关联的两个顶点i和j分别属于这两个不同的顶点集(i∈A, j∈B)，则称图G为一个二分图。

简单来说，如果图中所有顶点可以被分为两个集合，图中所有的边的头和尾不属于同一个顶点集合，而是跨越两个集合，则这个图是一个二分图。

我们再看一下这个图：

这个图乍一看不像是二分图，但是我们转化一下他的样子，就会发现它其实还是一个二分图

匈牙利算法

前置概念

匹配：在图论中，一个匹配（matching）是指一个边的集合，其中任意两条边都没有公共顶点。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突），但并非每个图都存在完美匹配。

交替路径：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径称为交替路径。

增广路径：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。

增广路径性质：

  1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M，因为两个端点分属两个集合，且未匹配。
  2. P经过取反操作可以得到一个更大的匹配M’。
  3. M为G的最大匹配当且仅当不存在相对于M的增广路径。

算法基本原理

匈牙利算法：利用增广路径求二分图的最大匹配算法称作匈牙利算法。（匈牙利数学家Edmonds于1965年提出）。

基本思想：通过寻找增广路径，把增广路径中的匹配边和非匹配边的相互交换，这样就会多出一条匹配边，直到找不到增广路径为止。

这里有一点要先确定好的是，这个过程是从已有边中找匹配边和非匹配边，不能创造新的边出来

我们以上面最后一个图为例来讲解一下整个算法的过程：

  1. 从顶点a出发，按照交替路径前进，第一个非匹配边为，到达顶点e，e为非匹配点，构成增广路径。令为匹配边，顶点a，e为匹配顶点。
  2. 从顶点b出发，第一非匹配边为，到达顶点e，选择匹配边，到达a，选择非匹配边，g为非匹配点，找到一条增广路径，交换增广路径中的匹配边与非匹配边，即b-e，a-g变为匹配边，a-e变为非匹配边。
  3. 从顶点c出发，第一非匹配边为，到达顶点e，然后按照交替路径前进，到达顶点b，无法继续前进，且b已经是匹配点了，所以没有找到新的增光路径
  4. 从顶点c出发，选择第二条非匹配边
  5. 从顶点d出发，选择非匹配边，到达顶点g，选择匹配边，到达顶点a，选择非匹配边到达顶点e，选择匹配边，到达顶部b，没有可以选择的边，且没有找到增广路径
  6. 继续从顶点d出发，选择非匹配边，找到增广路径，将边变为匹配边，算法结束。

最终我们的得到的结果为下图，下图中的红色线就是通过算法得到的最大匹配了：

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 顶点、边的编号均从 0 开始
// 邻接表储存

struct Edge
{
    int from;
    int to;
    int weight;

    Edge(int f, int t, int w):from(f), to(t), weight(w) {}
};

vector<int> G[__maxNodes]; /* G[i] 存储顶点 i 出发的边的编号 */
vector<Edge> edges;
typedef vector<int>::iterator iterator_t;
int num_nodes;
int num_left;
int num_right;
int num_edges;
int matching[__maxNodes]; /* 存储求解结果 */
int check[__maxNodes];

bool dfs(int u)
{
    for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 对 u 的每个邻接点
        int v = edges[*i].to;
        if (!check[v]) {     // 要求不在交替路中
            check[v] = true; // 放入交替路
            if (matching[v] == -1 || dfs(matching[v])) {
                // 如果是未盖点，说明交替路为增广路，则交换路径，并返回成功
                matching[v] = u;
                matching[u] = v;
                return true;
            }
        }
    }
    return false; // 不存在增广路，返回失败
}

int hungarian()
{
    int ans = 0;
    memset(matching, -1, sizeof(matching));
    for (int u=0; u < num_left; ++u) {
        if (matching[u] == -1) {
            memset(check, 0, sizeof(check));
            if (dfs(u))
                ++ans;
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
queue<int> Q;
int prev[__maxNodes];
int Hungarian()
{
    int ans = 0;
    memset(matching, -1, sizeof(matching));
    memset(check, -1, sizeof(check));
    for (int i=0; i<num_left; ++i) {
        if (matching[i] == -1) {
            while (!Q.empty()) Q.pop();
            Q.push(i);
            prev[i] = -1; // 设 i 为路径起点
            bool flag = false; // 尚未找到增广路
            while (!Q.empty() && !flag) {
                int u = Q.front();
                for (iterator_t ix = G[u].begin(); ix != G[u].end() && !flag; ++ix) {
                    int v = edges[*ix].to;
                    if (check[v] != i) {
                        check[v] = i;
                        Q.push(matching[v]);
                        if (matching[v] >= 0) { // 此点为匹配点
                            prev[matching[v]] = u;
                        } else { // 找到未匹配点，交替路变为增广路
                            flag = true;
                            int d=u, e=v;
                            while (d != -1) {
                                int t = matching[d];
                                matching[d] = e;
                                matching[e] = d;
                                d = prev[d];
                                e = t;
                            }
                        }
                    }
                }
                Q.pop();
            }
            if (matching[i] != -1) ++ans;
        }
    }
    return ans;
}

参考文章：https://www.cxyxiaowu.com/874.html