匈牙利算法 -hxw

二分图最大匹配算法（Hungarian Algorithm）

温馨提示： 这个算法的操作与原理及其数学证明都很繁与困难，建议理解如何应用以及应用场景即可

一、概论介绍

• 最大匹配:在二分图中最多能找到多少条没有公共端点的边（配对）

示例：
​

不难发现，这个二分图的最大匹配是如下（不唯一)

但是最大匹配数为 4

​​

• 下面我们严谨的表述一遍最大匹配：

在 G 的一个子图 M 中，M 的边集中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配

选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

• 下面介绍两个基本概念（交替路与增广路）

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

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

二、算法原理

原理： 由增广路的性质，增广路中的匹配边总是比未匹配边多一条，所以如果我们放弃一条增广路中的匹配边，选取未匹配边作为匹配边，则匹配的数量就会增加

匈牙利算法就是在不断寻找增广路，如果找不到增广路，就说明达到了最大匹配

可以数学证明这种算法得到的解即为最大匹配数

这个算法的严谨数学证明是比较难的，这里就不加以赘述了，感兴趣可以结合上学期离散数学的图论知识证明，不需要使用任何定理

举例使用：

起始状态尚未匹配，全部都是非匹配边和非匹配点

​​

任意选中 x1 与任意其中一个点 y1 匹配

​​

选中第二个点 x2，x1 没有已霸占 x2 的任何一个对象，故 x2 与任意一个 y2 匹配即可

​​

选中 x3，发现 x3 的第一对象 y1 已经被 x1 占了，于是找出 x3 出发的的交错路径 x3-y1-x1-y4，把交错路中已在匹配上的边 x1-y1 从匹配中去掉，反而匹配剩余的边 x3-y1，x1-y4，这就是增广路技巧

具体操作中将使用 DFS 深度优先搜索

接着选择 x4，发现没有增广路，于是只好选择 y3

​​

接着选择 x5,发现有增广路：x5-y4-x1-y1-x3-y7,于是变成如下

​​

最后选择 x6，x6 无对象可选，而且没有增广路，于是 x6 没法匹配

此结果即为最大匹配

Code-hxw

typedef struct tagMaxMatch{
    int edge[COUNT][COUNT];
    bool on_path[COUNT];
    int path[COUNT];
    int max_match;
}GRAPH_MATCH;
void outputRes(int *path){
    for (int i = 0 ; i<COUNT; i++) {
        printf("%d****%d\n",i,*(path+i));  
    }
}
void clearOnPathSign(GRAPH_MATCH *match){
    for (int j = 0 ; j < COUNT ; j++) {
        match->on_path[j] = false;
    }
}
//dfs算法
bool FindAugPath(GRAPH_MATCH *match , int xi){
  
    for (int yj = 0 ; yj < COUNT; yj++) {
        if ( match->edge[xi][yj] == 1 && !match->on_path[yj]) { 
             match->on_path[yj] = true;
            if (match->path[yj] == -1 || FindAugPath(match,match->path[yj])) { 
                  match->path[yj] = xi; 
                  return true;
            }
        }
    }
    return false;
}
void Hungary_match(GRAPH_MATCH *match){
    for (int xi = 0; xi<COUNT ; xi++) {
          FindAugPath(match, xi);
          clearOnPathSign(match);
    }
    outputRes(match->path);
}
int main() {
    GRAPH_MATCH *graph = (GRAPH_MATCH *)malloc(sizeof(GRAPH_MATCH));
    for (int i = 0 ; i < COUNT ; i++) {
        for (int j = 0 ; j < COUNT ; j++) {
            graph->edge[i][j] = 0;
        }
    }
    graph->edge[0][1] = 1;
    graph->edge[0][0] = 1;
    graph->edge[1][1] = 1;
    graph->edge[1][2] = 1;
    graph->edge[2][1] = 1;
    graph->edge[2][0] = 1;
    graph->edge[3][2] = 1;
//举例
    for (int j = 0 ; j < COUNT ; j++) {
        graph->path[j] = -1;
        graph->on_path[j] = false;
    }
    Hungary_match(graph);   
}

参考文献：

**[1]**​匈牙利算法（二分图） - 神犇(shenben) - 博客园 (cnblogs.com)

‍