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