作者：解学武

寻找二部图最大匹配的匈牙利数学家埃德蒙德斯在1965年提出的一个简化的最大流算法。该算法根据二部图匹配这个问题的特点将最大流算法进行了简化，提高了效率。

普通的最大流算法一般都是基于带权网络模型的，二部图匹配问题不需要区分图中的源点和汇点，也不关心边的方向，因此不需要复杂的网络图模型，这就是匈牙利算法简化的原因。

正是因为这个原因，匈牙利算法成为一种很简单的二分匹配算法，其基本流程是：

将图 G 最大匹配初始化为空
while(从Xi点开始在图G中找到新的增广路径)
{
    将增广路径假如到最大匹配中;
}
输出图 G 的最大匹配;

根据匈牙利算法的流程看，寻找图 G 中的增广路径是匈牙利算法的关键。先来看看什么是增广路径，二部图中的增广路径具有以下性质：

• 路径中边的条数是奇数；
• 路径的起点在二部图的左半边，终点在二部图的右半边；
• 路径上的点一个在左半边，一个在右半边，交替出现，整条路径上没有重复的点；
• 只有路径的起点和终点都是未覆盖的点，路径上其他的点都已经配对；
• 对路径上的边按照顺序编号，所有奇数编号的边都不在已知的匹配中，所有偶数编号的边都在已知的匹配中；
• 对增广路径进行“取反”操作，新的匹配数就比已知匹配数增加一个，也就是说，可以得到一个更大的匹配；

所谓的增广路径取反操作，就是把增广路径上奇数编号的边加入到已知匹配中，并把增广路径上偶数编号的边从已知匹配中删除。每做一次“取反”操作，得到的匹配就比原匹配多一个。

匈牙利算法的思路就是不停地寻找增广路径，增加匹配的个数，当不能再找到增广路径时，算法就结束了，得到的匹配就是最大匹配。

增广路径的起点总是在二部图的左边，因此寻找增广路径的算法总是从一侧的顶点开始，逐个顶点搜索。从 X_i 顶点开始搜索增广路径的流程如下：

while(从 X_i 的邻接表中找到下一个关联顶点 Y_j)
{
    if(顶点 Y_j 不在增广路径上)
    {
        将 Y_j 加入增广路径;
        if(Y_j 是未覆盖点或者从与 Y_j 相关连的顶点(X_k)能找到增广路径)
        {
            将 Y_j 的关联顶点修改为 X_i；
            从顶点 X_i 开始有增广路径，返回 true；
        }
    }
    从顶点 X_i 开始没有增广路径，返回 false；
}

在这个算法流程中，“从与 Y_j 相关连的顶点（X_k）能找到增广路径”这一步体现的是一个递归过程。因为如果之前的搜索已经将 Y_j 加入到增广路径中，说明 Y_j 在 X 集合中一定有一个关联点，我们假设 Y_j 在 X 集合中的这个关联点是 X_k，所以要从 X_k 开始继续寻找增广路径。当从 X_k 开始的递归搜索完成后，通过“将 Y_j 的关联顶点修改为 X_i”这一步操作，将其与 X_i 连在一起，形成一条更长的增广路径。

到现在为止，匈牙利算法的流程已经很清楚了，现在我们来给出实现代码。

首先定义求最大匹配的数据结构，这个数据结构要能表示二部图的边的关系，还要能体现最终的增广路径结果，给出如下定义：

typedef struct tagMaxMatch
{
    int edge[UNIT_COUNT][UNIT_COUNT];
    bool on_path[UNIT_COUNT];
    int path[UNIT_COUNT];
    int max_match;
}GRAPH_MATCH;

edge 是顶点与边的关系表，用来表示二部图，on_path 用来表示顶点 Y_j 是否已经在当前搜索过程中形成的增广路径上了，path 是当前找到的增广路径，max_match 是当前增广路径中边的条数，当算法结束时，如果 max_match 不等于顶点个数，说明有顶点不在最大增广路径上，也就是说，找不到能覆盖所有点的增广路径，此二部图没有最大匹配。

从 X_i 寻找增广路径的算法实现如下：

bool FindAugmentPath(GRAPH_MATCH *match, int xi)
{
    for(int yj = 0; yj < UNIT_COUNT; yj++)
    {
        if((match->edge[xi][yj] == 1) && !match->on_path[yj])
        {
            match->on_path[yj] = true;
            if( (match->path[yj] == -1)
                || FindAugmentPath(match, match->path[yj]) )
            {
                match->path[yj] = xi;
                return true;
            }
        }
    }
    return false;
}

算法实现基本上是按照之前的算法流程实现的，不需要做特别说明，唯一需要注意的是 path 中存放增广路径的方式。读者可能已经注意到了，存放的方式是以 Y 集合中的顶点为索引存放，其值是对应的关联顶点在 X 集合中的索引。搜索是按照 X 集合中的顶点索引进行的，增广路径以 Y 集合中的顶点为索引存储，关系是反的。

输出结果的时候，需要结合 Y 集合中的顶点索引输出，如果需要以 X 集合的顺序输出结果，需要反向转换，转换的方法非常简单：

int path[UNIT_COUNT] = { 0 };
for(int i = 0; i < match->max_match; i++)
{
    path[match->path[i]] = i;
}

转换后 path 中就是以 X 集合的顺序存放的结果。结合之前给出的匈牙利算法基本流程，最后给出匈牙利算法的入口函数实现：

bool Hungary_Match(GRAPH_MATCH *match)
{
    for(int xi = 0; xi < UNIT_COUNT; xi++)
    {
        if(FindAugmentPath(match, xi))
        {
            match->max_match++;
        }

        ClearOnPathSign(match);
    }
    return (match->max_match == UNIT_COUNT);
}

每完成一个顶点的搜索，需要重置 Y 集合中相关顶点的 on_path 标志，ClearOnPathSign() 函数就负责干这个事情。
我们用图 1 中的二部图数据初始化 GRAPH_MATCH 中的顶点关系表 edge，然后调用 Hungary_Match() 函数得到一组匹配：

X1<--->Y3
X2<--->Y1
X3<--->Y4
X4<--->Y2
X5<--->Y5

结果与图 2 一致，因为这个最大匹配没有未覆盖点，所以是完美匹配。
匈牙利算法的实现以顶点集合 V 为基础，每次 X 集合中选一个顶点 X_i 做增广路径的起点搜索增广路径。搜索增广路径需要遍历边集 E 内的所有边，遍历方法可以采用深度优先遍历（DFS），也可以采用广度优先遍历（BFS），无论什么方法，其时间复杂度都是 O(E)。

匈牙利算法每个顶点 V_i 只能选择一次，因此算法的整体时间复杂度是 O(V*E)，总的来说，是一个相当高效的算法。

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。