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

一、一些相关概念

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、最大独立集点数=总点数-最大匹配数