二分匹配——匈牙利算法；

结合自己在离散数学上所学的匹配知识，下面记录下自己对二分匹配的认识；

首先是匹配：无向图G=<V,E>匹配(边独立集：边的一个子集，子集中任意两条边不相邻（顶点不重合）（若干对不同事物之间的二元关系）

再就是二分图，指的是这样一种图，其所有顶点可以分成两个集合X和Y，其中X或Y中任意两个在同一集合中的点都不相连，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。给定一个二分图G，图中包含边数最多的匹配称为图的最大匹配。

下面是几个相关的定义：

设M是G中匹配
饱和点: v与M中边关联
非饱和点: v不与M中边关联
交错路径: 在M和E-M中交替取边的路径
可增广交错路径: 两端都是非饱和点的交错路径

如下图所示：前者为可增广交错路径，后者为扩展后的路径；

二分匹配——匈牙利算法；

二分匹配的一个常见问题就是求解最大匹配：

这里面最常用的就是匈牙利算法：

基本思想是：

从一个匹配开始
逐一检查不饱和点，对每一个不饱和点尝试寻找增广路径。（DFS/BFS）
得到更大的匹配
递归直到没有不饱和点或没有增广路径；

伪代码实现为：

for(每个不饱和点v)
{
path（v）
}

int Path(结点v)
{
for（每个与v邻接的结点u）
{
if(u不饱和 || path(与u的匹配的那个点))
{
v和u构成新匹配；
u原有的匹配取消；
return 1；
}
}
return 0；
}

根据伪代码可实现出匈牙利算法：
输入的格式为：

第1行3个整数，V1,V2的节点数目n1,n2,G的边数m
第2-m+1行，每行两个整数t1,t2，代表V1中编号为t1的点和V2中编号为t2的点之间有边相连
输出格式：
1个整数ans，代表最大匹配数

1，邻接矩阵表示图：

#include<iostream>
#include<cstring>
using namespace std;
int map[105][105];
int visit[105],flag[105];
int n,m;
bool dfs(int a) {
    for(int i=1;i<=n;i++) {
        if(map[a][i] && !visit[i]) {
            visit[i]=1;
            if(flag[i]==0 || dfs(flag[i])) {
                flag[i]=a;
                return true;
            }
        }
    }
    return false;
}
int main() {
    while(cin>>n>>m) {
        memset(map,0,sizeof(map));
        for(int i=1;i<=m;i++) {
            int x,y;
            cin>>x>>y;
            map[x][y]=1;
        }
        memset(flag,0,sizeof(flag));
        int result=0;
        for(int i=1;i<=n;i++) {
            memset(visit,0,sizeof(visit));
            if(dfs(i)) result++;
        }
        cout<<result<<endl;
    }
    return 0;
}

另附；邻接表表示图的匈牙利算法代码：

#include <iostream>
#include <cstring>
using namespace std;
//定义链表
struct link {
    int data; //存放数据
    link* next; //指向下一个节点
    link(int=0);
};
link::link(int n) {
    data=n;
    next=NULL;
}
int n1,n2,m,ans=0;
int result[101]; //记录n1中的点匹配的点的编号
bool state [101]; //记录n1中的每个点是否被搜索过
link *head [101]; //记录n2中的点的邻接节点
link *last [101]; //邻接表的终止位置记录
//判断能否找到从节点n开始的增广路
bool find(const int n) {
    link* t=head[n];
    while (t!=NULL) { //n仍有未查找的邻接节点时
        if (!(state[t->data])) { //如果邻接点t->data未被查找过
            state[t->data]=true; //标记t->data为已经被找过
            if ((result[t->data]==0) || //如果t->data不属于前一个匹配M
            (find(result[t->data]))) { //如果t->data匹配到的节点可以寻找到增广路
                result[t->data]=n; //那么可以更新匹配M'，其中n1中的点t->data匹配n
                return true; //返回匹配成功的标志
            }
        }
        t=t->next; //继续查找下一个n的邻接节点
    }
    return false;
}
int main() {
    int t1=0,t2=0;
    cin>>n1>>n2>>m;
    for (int i=0; i<m; i++) {
        cin>>t1>>t2;
        if (last[t1]==NULL)
            last[t1]=head[t1]=new link(t2);
        else
            last[t1]=last[t1]->next=new link(t2）；
    }
    for (int i=1; i<=n1; i++) {
        memset(state,0,sizeof(state));
        if (find(i)) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

秒客网

二分匹配——匈牙利算法；

相关文章