資源描述：
《二分圖最大匹配ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、程序設計協(xié)會第n次課…2015年5月左右匈牙利算法（二分圖的最大匹配算法）圖論算法之：二分圖問題：1.什么是二分圖？2.怎么判斷二分圖？二分圖染色法：匈牙利算法壯峰育磊RB大保健小婷芙蓉小月鳳姐匈牙利算法壯峰育磊RB大保健小婷芙蓉小月鳳姐匈牙利算法壯峰育磊RB大保健小婷芙蓉小月鳳姐匈牙利算法壯峰育磊RB大保健小婷芙蓉小月鳳姐匈牙利算法壯峰育磊RB大保健小婷芙蓉小月鳳姐匈牙利算法壯峰育磊RB大保健小婷芙蓉小月鳳姐匈牙利算法壯峰育磊RB大保健小婷芙蓉小月鳳姐匈牙利算法壯峰育磊RB大保健小婷芙蓉小月鳳姐匈牙利算
2、法壯峰育磊RB大保健小婷芙蓉小月鳳姐匈牙利算法壯峰育磊RB大保健小婷芙蓉小月鳳姐bool尋找從u出發(fā)的增廣路{for(從鄰接表中列舉u能到的頂點v){if(v不在增廣路上){把v加入增廣路;if(v是未蓋點或者從v的對應項出發(fā)有增廣路){修改v的對應項為u;返回true;}}}返回false;(從u的對應項出沒有增廣路)}void匈牙利hungary(){for(i=1->n){if(能尋找從i出發(fā)的增廣路)匹配數(shù)++;}輸出匹配數(shù);}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、大匹配數(shù)：最大匹配的匹配邊的數(shù)目最小頂點覆蓋：在二分圖中求最少的點,讓每條邊都至少和其中的一個點關聯(lián)。最小路徑覆蓋：用盡量少的不相交簡單路徑覆蓋有向無環(huán)圖的所有頂點。最大獨立集：在一個二分圖中,選擇一些頂點,使得所選擇的點集中任意兩個頂點之間沒有邊連。最小頂點覆蓋=最大匹配數(shù)最小路徑覆蓋=頂點數(shù)-最大匹配數(shù)最大獨立集=頂點數(shù)-最大匹配數(shù)杭電題庫：zhbit_二分圖最大匹配密碼：ac
