图论二分图匹配、最大匹配、完美匹配、匈牙利算法

78 阅读 0 评论 52 点赞

我是靠谱客的博主欢呼彩虹，最近开发中收集的这篇文章主要介绍图论二分图匹配、最大匹配、完美匹配、匈牙利算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

能够解决的问题

二分图匹配常常在指派问题的模型出现

概念

二分图的一个等价定义是：不含有「含奇数条边的环」的图。

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

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。（并非每个图都存在完美匹配）

做法

1、用匈牙利算法。
匈牙利算法是二分图匹配的核心算法，除了二分图多重匹配外均可使用。

2、用最大流
可以将二分图最大匹配问题看作是最大流问题的一种特殊情况。通过对原图进行变形，能够使得问题转换成最大流问题。

匈牙利算法

先要懂得几个概念

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。（注意是先经过非匹配边）

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

增广路的意义是改进匹配，因为增广路有一个重要特点：非匹配边比匹配边多一条。所以我们只要把增广路中的匹配边和非匹配边的身份进行交换即可，由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。而交换之后，匹配的边数会比原来多一条。所以我们不停地找增广路来增加匹配中的匹配边和匹配点。在找不到增广路时，也就达到了最大匹配（这是增广路定理）。这里可以用BFS或者DFS实现。

匈牙利树：一般由BFS构成，这棵树的叶子节点一定都是有匹配到的。

时间复杂度O（VE）

DFS的代码比较短，但是不够快
BFS的代码比较长，不过在稀疏图比DFS快很多。

代码

邻接矩阵

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 5;
bool G[MAXN][MAXN];//关系图
int match[MAXN];//
bool used[MAXN];//
int n;
bool dfs(int u)
{
for(int i = 0; i < n; ++i)
{
if(!used[i] && G[u][i])
{
used[i] = 1;
if(!match[i] || dfs(match[i]))
{
match[i] = u;
return true;
}
}
}
return false;
}
int Hungary()//匈牙利算法
{
int ans = 0;
//匹配数目
memset(match, 0, sizeof(match));
for(int i = 0; i < n; ++i)
{
memset(used, 0, sizeof(used));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
while(scanf("%d", &n) != EOF)
{
memset(G, false, sizeof(G));
for(int i = 0; i < n; ++i)
{
int u, v, t;
scanf("%d: (%d)", &u, &t);
for(int j = 1; j <= t; ++j)
{
scanf("%d", &v);
G[u][v] = true;
}
}
printf("%dn", n - Hungary() / 2);
}
return 0;
}

DFS代码（HDU 1086）（邻接表）

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 5;
int V;
//顶点数目
vector <int> G[MAXN];
//图的邻接表表示
int match[MAXN];
//所匹配到的点
bool used[MAXN];
//DFS中用到的访问标记
bool dfs(int v)//用DFS找增广路
{
used[v] = true;
for(int i = 0; i < G[v].size(); ++i)//对于
{
int u = G[v][i], w = match[u];
if(w < 0 || !used[w] && dfs(w))
{
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
int Hungary()//匈牙利算法
{
int res = 0;
memset(match, -1, sizeof(match));
for(int v = 0; v < V; ++v)
{
if(match[v] < 0)//如果我遇到了一个没有匹配的点，那么对这个点进行深搜，找找看它有没有增广路。
{
memset(used, 0, sizeof(used));
if(dfs(v))
{
res++;
}
}
}
return res;
}
int main()
{
while(scanf("%d", &V) != EOF)
{
for(int i = 0; i < V; ++i)
{
G[i].clear();
int u = i, v, t;
scanf("%d: (%d)", &t, &t);
for(int j = 0; j < t; ++j)
{
scanf("%d", &v);
G[u].push_back(v);
}
}
printf("%dn",
V - Hungary());
}
return 0;
}

BFS代码模板

#include <bits/stdc++.h>
using namespace std;
bool bfs(int st)
{
queue <int> q;
q.push(st);
pre[st] = -1;
bool flag = false;
while(!q.empty() && !flag) {
int u = q.front(); q.pop();
for(int i = head[u]; ~i && !flag; i = e[i].next) {
int v = e[i].v;
if(vis[v] != st) {
vis[v] = st;
q.push(my[v]);
if(~my[v]) pre[my[v]] = u;
else {
int a = u, b = v;
flag = true;
while(~a) {
int t = mx[a];
mx[a] = b;
my[b] = a;
a = pre[a];
b = t;
}
}
}
}
}
return mx[st] != -1;
}
int hungary()
{
int ret = 0;
memset(mx, -1, sizeof(mx));
memset(my, -1, sizeof(my));
memset(vis, -1, sizeof(vis));
for(int i = 1; i <= nX; i++) {//number from 1
if(mx[i] == -1) {
if(bfs(i)) ret++;
}
}
return ret;
}
int main()
{
return 0;
}

补充定义和定理

最大匹配数：最大匹配的匹配边的数目

最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择

最大独立集：选取最多的点，使任意所选两点均不相连。|最大独立集| = |V|-|最大匹配数|

最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。

定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）

定理2：最大独立数 = 点数 - 最大匹配数

定理3：最小路径覆盖数 = 顶点数 - 最大匹配数

参考来源

博客（推荐）
https://www.renfei.org/blog/bipartite-matching.html?tdsourcetag=s_pcqq_aiomsg
博客
https://blog.csdn.net/qq_41730082/article/details/81162561
白书P218