二分圖就不贅述了，我在知識(shí)資料整理有相關(guān)資料。

.最大匹配 ?.最小路徑覆蓋 ?.最小點(diǎn)覆蓋 ?.最大獨(dú)立集

最大匹配：二分圖中邊集最大的那個(gè)匹配

最小路徑（邊）覆蓋：用盡量小的不想交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)圖（DAG）G的所有頂點(diǎn)

最小頂點(diǎn)（點(diǎn)）覆蓋：用最少的點(diǎn)，讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)

最大獨(dú)立集：在N個(gè)點(diǎn)的圖中選出m個(gè)點(diǎn)，使這m個(gè)點(diǎn)兩兩之間沒(méi)有邊的點(diǎn)中，m的最大值

?

二分圖匹配模型，二分圖有如下幾種常見(jiàn)變形：

1.二分圖的最小頂點(diǎn)覆蓋

最小頂點(diǎn)覆蓋要求用最少的點(diǎn)（x或y中的都行），讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)

knoig定理：二分圖中最小頂點(diǎn)覆蓋等于最大匹配數(shù)

?

2.DAG圖中的最小路徑覆蓋

用盡量少的不相交簡(jiǎn)單路徑覆蓋DAG的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問(wèn)題

結(jié)論：DAG圖中的最小路徑覆蓋數(shù) = 節(jié)點(diǎn)數(shù)（n）-最大匹配數(shù)（m）

?

3.二分圖的最大獨(dú)立集

最大獨(dú)立問(wèn)題：在n個(gè)點(diǎn)的圖G中選出m個(gè)點(diǎn)，使這m個(gè)點(diǎn)兩兩之間沒(méi)有邊，求m的最大值

結(jié)論：二分圖的最大獨(dú)立集數(shù) = 節(jié)點(diǎn)數(shù)（n）-最大匹配數(shù)（m）

?

有一種很經(jīng)典的二分圖模型，在一個(gè)n*n的矩陣中，這個(gè)矩陣?yán)锩嬗衚個(gè)障礙物，你擁有一把武器，一發(fā)彈藥一次能消滅一行或者一列的障礙物，求消滅全部障礙物所需的最少?gòu)椝帞?shù)。

可以這樣考慮：我們以所有行為二分圖的左頂點(diǎn)，所有的列為右頂點(diǎn)，那么如果位于坐標(biāo)p（x，y）有障礙物，我們就連一條邊，然后我們只需要最少的頂點(diǎn)覆蓋所有的邊即可。這樣就是二分圖的最小頂點(diǎn)覆蓋問(wèn)題了，我們又知道最大小頂點(diǎn)等于二分圖最大匹配。

?

?

時(shí)間復(fù)雜度： 鄰接矩陣：?O(n³)
鄰接表： O(nm) 空間復(fù)雜度： 鄰接矩陣：?O(n²)
鄰接表：O(n+m)

?

/**************************************************** 二分圖匹配（匈牙利算法的DFS實(shí)現(xiàn)） INIT：g[][]兩邊定點(diǎn)劃分的情況 CALL:res=hungary();輸出最大匹配數(shù) 優(yōu)點(diǎn)：適于稠密圖，DFS找增廣路快，實(shí)現(xiàn)簡(jiǎn)潔易于理解 時(shí)間復(fù)雜度:O(VE); ****************************************************/ const int MAXN=1000; int uN,vN; //u,v數(shù)目 int g[MAXN][MAXN];//編號(hào)是0~n-1的 int linker[MAXN]; bool used[MAXN]; bool dfs(int u) {int v;for(v=0;v<vN;v++)if(g[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||dfs(linker[v])){linker[v]=u;return true;} } return false; } int hungary() {int res=0;int u;memset(linker,-1,sizeof(linker));for(u=0;u<uN;u++){memset(used,0,sizeof(used));if(dfs(u)) res++;} return res; } 最大匹配——匈牙利算法

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Roni-i/p/7475175.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的二分图-匈牙利算法模板的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。