本文主要是介绍二部图总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天总结一下二部图，那么首先谈一下二部图的用处，首先谈一下二部图的最大匹配一下是代码模型
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max 100
bool match[Max][Max];
int pre[Max];
bool vi[Max];
int find(int x);
int n,m,k;
int main()
{while(scanf("%d%d",&n,&m),n,m){int i,a,b;memset(match,false,sizeof(match));memset(pre,-1,sizeof(int)*(n+1));scanf("%d",&k);for(i=0;i<k;i++){scanf("%d%d",&a,&b); //a代表m的编号，b代表n的编号match[a][b]=true;}int ans=0;for(i=1;i<=m;i++){memset(vi,false,sizeof(n+1));if(find(i))ans++;printf("%d\n",ans);}}return 0;
}
int find(int x)
{int i;for(i=1;i<=n;i++){if(match[x][i]&& !vi[i]){vi[i]=true;if(pre[i]==-1 || find(pre[i])){pre[i]=x;return true;}}}return false;
}匈牙利算法为核心
下面是二部图的最小顶点覆盖=二部图的最大匹配
二部图的最大点独立集=顶点数-二部图的最大匹配
DAG图的最小路径覆盖=顶点数-相应二部图的最大匹配
其中重点谈一下DAG图的最小路径覆盖，定义:用尽量少的不相交简单路径覆盖有向无环图中的所有顶点
什么叫做不相交，指的是终点不能重合，否则就是另外一条路径了，这样的最小的路径数就是最小路径覆盖了
我们可以将这类问题，从有向图转化为无向图，那么有向线段的起点为二部图的一边，而终点为二部图的另一边，这样来构建二部图
归结起来就是求二部图的最大匹配，所以二部图的最大匹配才是王道......
那么最小顶点覆盖和最大点独立集的应用都好理解
什么时候用的到DAG图的最小路径覆盖呢？
一般在所描述的问题可以转化为DAG图时，要求此图为有向无环，注意无环是有向图的无环......
这篇关于二部图总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
