二分图最大匹配ppt课件.ppt

《二分图最大匹配ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计协会第n次课…2015年5月左右匈牙利算法（二分图的最大匹配算法）图论算法之：二分图问题：1.什么是二分图？2.怎么判断二分图？二分图染色法：匈牙利算法壮峰育磊RB大保健小婷芙蓉小月凤姐匈牙利算法壮峰育磊RB大保健小婷芙蓉小月凤姐匈牙利算法壮峰育磊RB大保健小婷芙蓉小月凤姐匈牙利算法壮峰育磊RB大保健小婷芙蓉小月凤姐匈牙利算法壮峰育磊RB大保健小婷芙蓉小月凤姐匈牙利算法壮峰育磊RB大保健小婷芙蓉小月凤姐匈牙利算法壮峰育磊RB大保健小婷芙蓉小月凤姐匈牙利算法壮峰育磊RB大保健小婷芙蓉小月凤姐匈牙利算

2、法壮峰育磊RB大保健小婷芙蓉小月凤姐匈牙利算法壮峰育磊RB大保健小婷芙蓉小月凤姐bool寻找从u出发的增广路{for(从邻接表中列举u能到的顶点v){if(v不在增广路上){把v加入增广路;if(v是未盖点或者从v的对应项出发有增广路){修改v的对应项为u;返回true;}}}返回false;(从u的对应项出没有增广路)}void匈牙利hungary(){for(i=1->n){if(能寻找从i出发的增广路)匹配数++;}输出匹配数;}boolFindPath(intu){for(intv=1;v<=n;

3、v++){if(G[u][v]==1){if(!vis[v]){vis[v]=true;if(link[v]==-1

4、

5、FindPath(link[v])){link[v]=u;returntrue;}}}}returnfalse;}inthungary(){intans=0;memset(link,-1,sizeof(link));for(inti=1;i<=n;i++){memset(vis,0,sizeof(vis));if(FindPath(i))ans++;}returnans;}补充知识点：最

6、大匹配数：最大匹配的匹配边的数目最小顶点覆盖：在二分图中求最少的点,让每条边都至少和其中的一个点关联。最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图的所有顶点。最大独立集：在一个二分图中,选择一些顶点,使得所选择的点集中任意两个顶点之间没有边连。最小顶点覆盖=最大匹配数最小路径覆盖=顶点数-最大匹配数最大独立集=顶点数-最大匹配数杭电题库：zhbit_二分图最大匹配密码：ac