欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图论算法----二分图匹配----匈牙利算法详解

程序员文章站 2022-04-16 13:25:14
...

一、一些相关概念

1、二分图的概念:

二分图又称作二部图,是图论中的一种特殊模型。

设G=(V,E)是一个无向图。
如果顶点集V可分割为两个互不相交的子集X和Y,并且图中每条边连接的两个顶点一个在X中,另一个在Y中,则称图G为二分图。

2、判断二分图的方法:
一个图是连通的,可以用如下的方法判定是否是二分图:
(1)在图中任选一顶点v,定义其距离标号为0,然后把它的邻接点的距离标号均设为1,接着把所有标号为1的邻接点均标号为2(如果该点未标号的话),以此类推。
(2)标号过程可以用一次BFS实现。标号后,所有标号为奇数的点归为X部,标号为偶数的点归为Y部。
(3)接下来,二分图的判定就是依次检查每条边,看两个端点是否是一个在X部,一个在Y部。
如果一个图不连通,则在每个连通块中作判定。

3、二分图匹配的概念:
给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。
图论算法----二分图匹配----匈牙利算法详解
图中红色的边是数量为2的匹配。
图论算法----二分图匹配----匈牙利算法详解

4、最大匹配的概念:
选择边数最大的子图M称为图的最大匹配问题

若二分图X部的每一个顶点都与Y中的一个顶点匹配,并且Y部中的每一个顶点也与X部中的一个顶点匹配,则该匹配为完美匹配。

如果一个二分图,X部中的每一个顶点都与Y部中的一个顶点匹配,或者Y部中的每一个顶点也与X部中的一个顶点匹配,则该匹配为完备匹配。

图中所示为一个最大匹配,也是完备匹配,但不是完美匹配。
图论算法----二分图匹配----匈牙利算法详解


5、增广路径的概念:
设M为二分图G已匹配边的集合,若P是图G中一条连通两个未匹配顶点的路径(P的起点在X部,终点在Y部,反之亦可),并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。
增广路径是一条“交错轨”。也就是说,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有参与匹配......最后一条边没有参与匹配,并且起点和终点还没有被选择过
图论算法----二分图匹配----匈牙利算法详解
如图,增广路径为C->I->E->F->A->H。

那么,增广路径有什么用呢?我们发现,把增广路径的所有边取反(即匹配的变成未匹配,未匹配的边成匹配),
则子图M的边数会加1,当找不到增广路径时,这就是最大匹配了。
图论算法----二分图匹配----匈牙利算法详解


6、增广路径的性质:

(1)增广路径的长度必定为奇数,第一条边和最后一条边都不属于M,因为两个端点分属两个集合,且未匹配。

(2)把一条增广路径经过取反操作可以得到一个更大的匹配M’。

(3)M为G的最大匹配当且仅当不存在相对于M的增广路径。


7、匈牙利算法:

算*廓:

(1)置M为空

(2)找出一条增广路径P,通过取反操作获得更大的匹配M’代替M

(3)重复(2)操作直到找不出增广路径为止


我们采用DFS的办法找一条增广路径:
从X部一个未匹配的顶点u开始,找一个未访问的邻接点v(v一定是Y部顶点)。对于v,分两种情况:

(1)如果v未匹配,则已经找到一条增广路

(2)如果v已经匹配,则取出v的匹配顶点w(w一定是X部顶点),边(w,v)目前是匹配的,根据“取反”的想法,要将(w,v)改为未匹配,(u,v)设为匹配,能实现这一点的条件是看从w为起点能否找到一条增广路径P’。如果行,则u-v-P’就是一条以u为起点的增广路径。

代码:(有许多写法)

int w[202][202],cx[202],cy[202],nx,ny;
bool visit[202];
bool dfs(int u)
{
    for(int i=1;i<=w[u][0];i++){
        int v=w[u][i];
        if(visit[v]==0){
            visit[v]=1;
            if(cy[v]==-1||dfs(cy[v])){
                cx[u]=v;cy[v]=u;
                return true;
            }
        }
    }
    return false;
}
int maxmatch()
{
    int ans=0;
    memset(cx,-1,sizeof(cx));
    memset(cy,-1,sizeof(cy));
    for(int i=0;i<=nx;i++){
        if(cx[i]==-1){ 
            memset(visit,0,sizeof(visit));
            ans+=dfs(i); 
        }
    }
    return ans;
}

8、匈牙利算法的时空分析:

时间复杂度:

找一次增广路径的时间为:

邻接矩阵: O(n^2)

邻接表:O(n+m)

总时间:

邻接矩阵:O(n^3)

       邻接表:O(n*m)

空间复杂度:

  邻接矩阵:O(n^2)

  邻接表:   O(m+n)



二、几个有关结论
1、最少点覆盖集的点数就是最大匹配数M。
2、最少边覆盖集的边数=总边数-最大匹配数
3、最大独立集点数=总点数-最大匹配数