【图论】匈牙利算法与KM算法（寻找二部图最佳匹配与最佳完备匹配）

53 阅读 0 评论 35 点赞

我是靠谱客的博主神勇茉莉，最近开发中收集的这篇文章主要介绍【图论】匈牙利算法与KM算法（寻找二部图最佳匹配与最佳完备匹配），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

匈牙利算法

对于一个二分图，如何找到其最大匹配，也就是匹配数最大的匹配？

答案便是匈牙利算法，它利用增广路径来求二分图最大匹配。我们通过一个例子来更好地说明二分图的情况。

思路：

假设有3个男生3个女生，现在我们要帮他们做配对（男生不可以互相喜欢，女生也一样），如果没有任何限制，即男生对女生没有任何要求，女生对男生也没有任何要求，那显然最大匹配就是3对啦。而情况通常是，每个男生喜欢某些女生而不喜欢其他女生。比如男1喜欢女1和女2，男2喜欢女1和女3，男3喜欢女2和女3.现在我们跑一遍匈牙利算法。

首先匹配男1，搜索到女1还没有被匹配，则匹配之，并将女1标记为已匹配。接下来匹配男2，搜索到女1已经被匹配，这时男2很失望，便询问男1能否将这个女生让给他，去寻找另外一位女生匹配。男1答应了，于是找到了女2。于是现在男1跟女2匹配，男2跟女1匹配。现在我们匹配男3，男3喜欢女2和女3，首先搜索到女2，发现女2跟男1配对了，便询问男1能否找到另外的匹配。男1又找到女1发现女1跟男2匹配了，又去询问男2能否找到另外的匹配，男2说好，于是找到了女3跟他匹配。于是他回复男1说找到了，男1又回复男2说找到了。这样结局皆大欢喜，男1匹配了女1,男2匹配了女3，男3匹配了女2。而上面那些询问的过程，便是寻找增广路径的过程。如果能找到，则匹配总数加1

具体代码如下：

int n,m;//顶点数n和边数m
int e[51][51];//一张图
int vis[51];
int match[51];//标记谁匹配谁
int dfs(int u)
{
int i;
for(i=1;i<=n;i++)
{
if(vis[i]==0&&e[u][i]==1)//这个点还没去过，而且他们之间可以连通
{
vis[1]=1;//把点标记为已经尝试
if(match[i]==0||dfs(match[i]))//这个点还没有被匹配或者它匹配的点可以去匹配其他人
{
match[u]=i;
match[i]=u;
return 1;
}
}
}
return 0;
}

for(i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
{
tot++;//若能找到新的匹配，则总数+1
}
}

KM算法：

现在假设男生对女生之间不再是单纯的喜欢就好，男生对女生有自己的排名，即对每个女生有不同的期望值，每个男生都希望跟期望

值最高的女生匹配，这就难免出现冲突的情况，比如众屌丝都喜欢同一个女神。在这种情况下，我们如何找到一种最大的匹配，并且

使得每个人获得的期望值总和最大呢？

这是KM算法要解决的问题，KM算法求的是完备匹配下的最大权匹配：

在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。

我们先贴出代码，再根据代码来讲解。

int w[1005][1005];
const int inf=(1<<20)-1;
int m,n;//n左m右
int cx[1005],cy[1005];//顶标
bool usex[1005],usey[1005];
int link[1005];//link[i]=x代表：在y图中的i与x相连
bool dfs(int u){
usex[u]=1;
for(int i=1;i<=m;i++)
if(!usey[i]&&cx[u]+cy[i]==w[u][i]){
usey[i]=1;
if(link[i]==-1||dfs(link[i])){
link[i]=u;
return 1;
}
}
return 0;
}
int KM(){
memset(cy,0,sizeof(cy));
memset(cx,-1,sizeof(cx));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cx[i]=max(cx[i],w[i][j]);
for(int i=1;i<=n;i++){
while(1){
int d=inf;
memset(usex,0,sizeof(usex));
memset(usey,0,sizeof(usey));
if(dfs(i))break;
for(int i=1;i<=n;i++)
{
if(usex[i])
{
for(int j=1;j<=m;j++)
{
if(!usey[j])
d=min(d,cx[i]+cy[j]-w[i][j]);
}
}
}
if(d==inf)return -1;
for(int i=1;i<=n;i++)
if(usex[i])cx[i]-=d;
for(int i=1;i<=m;i++)
if(usey[i])cy[i]+=d;
}
}
int ans=0;
for(int i=1;i<=m;i++){
if(~link[i])ans+=w[link[i]][i];
}
return ans;
}

KM算法代码讲解：

首先，x和y可以看成是男生和女生，有一个cx，cy数组，可以看成是男生对女生，女生对男生的期望值。KM算法1到5行，我们对cx,

cy进行了初始化。一开始男生肯定是希望跟期望值最高的女生匹配，所以cx初始化为最大的期望值。而女生则对此没什么所谓，期望

值全是0。

接下来遍历整个男生组，对每个男生进行匹配。一开始便进入一个死循环，首先usex和usey全部初始化为0,开始寻找男1的匹配女生。

在dfs中，我们看到结构跟匈牙利算法中的DFS结构差不多，唯一区别是多了一个cx[u]+cy[i]==w[u][i]。这个是什么意思呢？由于一开

始每个男生都想和期望值最高的女生匹配，所以一开始cx[u]+cy[i]肯定是等于那个最大期望值啦。当它等于w[u][i]，也就是找到那个女

生后，则进行匹配。

假设男1和女2匹配了。现在我们匹配男2，他也想和女2匹配，询问他能不能去匹配另外一个人。这时男1找遍所有都没有符合条件的

（因为此时男1最高的期望值是女2，而现在不能匹配女2了），因此函数返回-1，回到KM算法中，不会跳出死循环，而是进入了下面

一个操作。这个操作便是KM算法的精髓。它遍历所有已经访问过的x和所有没被访问过的y，计算出最小的cx[i]+cy[j]-w[i][j]。这个值

是什么意思呢？因为男1不能再匹配他的女神了，那么他就要把自己的期望值降低，去寻找期望值排第二的女生，那么这个期望值应