學(xué)算法認(rèn)準(zhǔn) labuladong

點(diǎn)擊卡片可搜索關(guān)鍵詞👇

讀完本文，可以去力扣解決如下題目：

785. 判斷二分圖（中等）

886. 可能的二分法（中等）

我之前寫了好幾篇圖論相關(guān)的文章：

東哥帶你刷圖論第一期：圖遍歷算法

東哥帶你刷圖論第二期：環(huán)檢測和拓?fù)渑判?/p>

東哥帶你刷圖論第三期：Dijkstra 最短路徑算法

除此之外，并查集算法計(jì)算連通分量名流問題?也和圖結(jié)構(gòu)有一些相關(guān)性。

那么今天繼續(xù)來講一個(gè)經(jīng)典圖論算法：二分圖判定算法。

二分圖簡介

在講二分圖的判定算法之前，我們先來看下百度百科對「二分圖」的定義：

二分圖的頂點(diǎn)集可分割為兩個(gè)互不相交的子集，圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬于這兩個(gè)子集，且兩個(gè)子集內(nèi)的頂點(diǎn)不相鄰。

其實(shí)圖論里面很多術(shù)語的定義都比較拗口，不容易理解。我們甭看這個(gè)死板的定義了，來玩?zhèn)€游戲吧：

給你一幅「圖」，請你用兩種顏色將圖中的所有頂點(diǎn)著色，且使得任意一條邊的兩個(gè)端點(diǎn)的顏色都不相同，你能做到嗎？

這就是圖的「雙色問題」，其實(shí)這個(gè)問題就等同于二分圖的判定問題，如果你能夠成功地將圖染色，那么這幅圖就是一幅二分圖，反之則不是：

在具體講解二分圖判定算法之前，我們先來說說計(jì)算機(jī)大佬們閑著無聊解決雙色問題的目的是什么。

首先，二分圖作為一種特殊的圖模型，會被很多高級圖算法（比如最大流算法）用到，不過這些高級算法我們不是特別有必要去掌握，有興趣的讀者可以自行搜索。

從簡單實(shí)用的角度來看，二分圖結(jié)構(gòu)在某些場景可以更高效地存儲數(shù)據(jù)。

比如前文 介紹《算法 4》

如果用哈希表存儲，需要兩個(gè)哈希表分別存儲「每個(gè)演員到電影列表」的映射和「每部電影到演員列表」的映射。

但如果用「圖」結(jié)構(gòu)存儲，將電影和參演的演員連接，很自然地就成為了一幅二分圖：

每個(gè)電影節(jié)點(diǎn)的相鄰節(jié)點(diǎn)就是參演該電影的所有演員，每個(gè)演員的相鄰節(jié)點(diǎn)就是該演員參演過的所有電影，非常方便直觀。

類比這個(gè)例子，其實(shí)生活中不少實(shí)體的關(guān)系都能自然地形成二分圖結(jié)構(gòu)，所以在某些場景下圖結(jié)構(gòu)也可以作為存儲鍵值對的數(shù)據(jù)結(jié)構(gòu)（符號表）。

好了，接下來進(jìn)入正題，說說如何判定一幅圖是否是二分圖。

二分圖判定思路

判定二分圖的算法很簡單，就是用代碼解決「雙色問題」。

說白了就是遍歷一遍圖，一邊遍歷一遍染色，看看能不能用兩種顏色給所有節(jié)點(diǎn)染色，且相鄰節(jié)點(diǎn)的顏色都不相同。

既然說到遍歷圖，也不涉及最短路徑之類的，當(dāng)然是 DFS 算法和 BFS 皆可了，DFS 算法相對更常用些，所以我們先來看看如何用 DFS 算法判定雙色圖。

首先，基于 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的框架思維

/*?二叉樹遍歷框架?*/ void?traverse(TreeNode?root)?{if?(root?==?null)?return;traverse(root.left);traverse(root.right); }/*?多叉樹遍歷框架?*/ void?traverse(Node?root)?{if?(root?==?null)?return;for?(Node?child?:?root.children)traverse(child); }/*?圖遍歷框架?*/ boolean[]?visited; void?traverse(Graph?graph,?int?v)?{//?防止走回頭路進(jìn)入死循環(huán)if?(visited[v])?return;//?前序遍歷位置，標(biāo)記節(jié)點(diǎn)?v?已訪問visited[v]?=?true;for?(TreeNode?neighbor?:?graph.neighbors(v))traverse(graph,?neighbor); }

因?yàn)閳D中可能存在環(huán)，所以用visited數(shù)組防止走回頭路。

這里可以看到我習(xí)慣把 return 語句都放在函數(shù)開頭，因?yàn)橐话?return 語句都是 base case，集中放在一起可以讓算法結(jié)構(gòu)更清晰。

其實(shí)，如果你愿意，也可以把 if 判斷放到其它地方，比如圖遍歷框架可以稍微改改：

/*?圖遍歷框架?*/ boolean[]?visited; void?traverse(Graph?graph,?int?v)?{//?前序遍歷位置，標(biāo)記節(jié)點(diǎn)?v?已訪問visited[v]?=?true;for?(int?neighbor?:?graph.neighbors(v))?{if?(!visited[neighbor])?{//?只遍歷沒標(biāo)記過的相鄰節(jié)點(diǎn)traverse(graph,?neighbor);}} }

這種寫法把對visited的判斷放到遞歸調(diào)用之前，和之前的寫法唯一的不同就是，你需要保證調(diào)用traverse(v)的時(shí)候，visited[v] == false。

為什么要特別說這種寫法呢？因?yàn)槲覀兣袛喽謭D的算法會用到這種寫法。

回顧一下二分圖怎么判斷，其實(shí)就是讓traverse函數(shù)一邊遍歷節(jié)點(diǎn)，一邊給節(jié)點(diǎn)染色，嘗試讓每對相鄰節(jié)點(diǎn)的顏色都不一樣。

所以，判定二分圖的代碼邏輯可以這樣寫：

/*?圖遍歷框架?*/ void?traverse(Graph?graph,?boolean[]?visited,?int?v)?{visited[v]?=?true;//?遍歷節(jié)點(diǎn)?v?的所有相鄰節(jié)點(diǎn)?neighborfor?(int?neighbor?:?graph.neighbors(v))?{if?(!visited[neighbor])?{//?相鄰節(jié)點(diǎn)?neighbor?沒有被訪問過//?那么應(yīng)該給節(jié)點(diǎn)?neighbor?涂上和節(jié)點(diǎn)?v?不同的顏色traverse(graph,?visited,?neighbor);}?else?{//?相鄰節(jié)點(diǎn)?neighbor?已經(jīng)被訪問過//?那么應(yīng)該比較節(jié)點(diǎn)?neighbor?和節(jié)點(diǎn)?v?的顏色//?若相同，則此圖不是二分圖}} }

如果你能看懂上面這段代碼，就能寫出二分圖判定的具體代碼了，接下來看兩道具體的算法題來實(shí)操一下。

題目實(shí)踐

力扣第 785 題「判斷二分圖」就是原題，題目給你輸入一個(gè) 鄰接表 表示一幅無向圖，請你判斷這幅圖是否是二分圖。

函數(shù)簽名如下：

boolean?isBipartite(int[][]?graph);

比如題目給的例子，輸入的鄰接表graph = [[1,2,3],[0,2],[0,1,3],[0,2]]，也就是這樣一幅圖：

顯然無法對節(jié)點(diǎn)著色使得每兩個(gè)相鄰節(jié)點(diǎn)的顏色都不相同，所以算法返回 false。

但如果輸入graph = [[1,3],[0,2],[1,3],[0,2]]，也就是這樣一幅圖：

如果把節(jié)點(diǎn){0, 2}涂一個(gè)顏色，節(jié)點(diǎn){1, 3}涂另一個(gè)顏色，就可以解決「雙色問題」，所以這是一幅二分圖，算法返回 true。

結(jié)合之前的代碼框架，我們可以額外使用一個(gè)color數(shù)組來記錄每個(gè)節(jié)點(diǎn)的顏色，從而寫出解法代碼：

//?記錄圖是否符合二分圖性質(zhì) private?boolean?ok?=?true; //?記錄圖中節(jié)點(diǎn)的顏色，false?和?true?代表兩種不同顏色 private?boolean[]?color; //?記錄圖中節(jié)點(diǎn)是否被訪問過 private?boolean[]?visited;//?主函數(shù)，輸入鄰接表，判斷是否是二分圖 public?boolean?isBipartite(int[][]?graph)?{int?n?=?graph.length;color?=??new?boolean[n];visited?=??new?boolean[n];//?因?yàn)閳D不一定是聯(lián)通的，可能存在多個(gè)子圖//?所以要把每個(gè)節(jié)點(diǎn)都作為起點(diǎn)進(jìn)行一次遍歷//?如果發(fā)現(xiàn)任何一個(gè)子圖不是二分圖，整幅圖都不算二分圖for?(int?v?=?0;?v?<?n;?v++)?{if?(!visited[v])?{traverse(graph,?v);}}return?ok; }//?DFS?遍歷框架 private?void?traverse(int[][]?graph,?int?v)?{//?如果已經(jīng)確定不是二分圖了，就不用浪費(fèi)時(shí)間再遞歸遍歷了if?(!ok)?return;visited[v]?=?true;for?(int?w?:?graph[v])?{if?(!visited[w])?{//?相鄰節(jié)點(diǎn)?w?沒有被訪問過//?那么應(yīng)該給節(jié)點(diǎn)?w?涂上和節(jié)點(diǎn)?v?不同的顏色color[w]?=?!color[v];//?繼續(xù)遍歷?wtraverse(graph,?w);}?else?{//?相鄰節(jié)點(diǎn)?w?已經(jīng)被訪問過//?根據(jù)?v?和?w?的顏色判斷是否是二分圖if?(color[w]?==?color[v])?{//?若相同，則此圖不是二分圖ok?=?false;}}} }

這就是解決「雙色問題」的代碼，如果能成功對整幅圖染色，則說明這是一幅二分圖，否則就不是二分圖。

接下來看一下 BFS 算法的邏輯：

//?記錄圖是否符合二分圖性質(zhì) private?boolean?ok?=?true; //?記錄圖中節(jié)點(diǎn)的顏色，false?和?true?代表兩種不同顏色 private?boolean[]?color; //?記錄圖中節(jié)點(diǎn)是否被訪問過 private?boolean[]?visited;public?boolean?isBipartite(int[][]?graph)?{int?n?=?graph.length;color?=??new?boolean[n];visited?=??new?boolean[n];for?(int?v?=?0;?v?<?n;?v++)?{if?(!visited[v])?{//?改為使用?BFS?函數(shù)bfs(graph,?v);}}return?ok; }//?從?start?節(jié)點(diǎn)開始進(jìn)行?BFS?遍歷 private?void?bfs(int[][]?graph,?int?start)?{Queue<Integer>?q?=?new?LinkedList<>();visited[start]?=?true;q.offer(start);while?(!q.isEmpty()?&&?ok)?{int?v?=?q.poll();//?從節(jié)點(diǎn)?v?向所有相鄰節(jié)點(diǎn)擴(kuò)散for?(int?w?:?graph[v])?{if?(!visited[w])?{//?相鄰節(jié)點(diǎn)?w?沒有被訪問過//?那么應(yīng)該給節(jié)點(diǎn)?w?涂上和節(jié)點(diǎn)?v?不同的顏色color[w]?=?!color[v];//?標(biāo)記?w?節(jié)點(diǎn)，并放入隊(duì)列visited[w]?=?true;q.offer(w);}?else?{//?相鄰節(jié)點(diǎn)?w?已經(jīng)被訪問過//?根據(jù)?v?和?w?的顏色判斷是否是二分圖if?(color[w]?==?color[v])?{//?若相同，則此圖不是二分圖ok?=?false;}}}} }

核心邏輯和剛才實(shí)現(xiàn)的traverse函數(shù)（DFS 算法）完全一樣，也是根據(jù)相鄰節(jié)點(diǎn)v和w的顏色來進(jìn)行判斷的。關(guān)于 BFS 算法框架的探討，詳見前文 BFS 算法框架Dijkstra 算法模板

最后再來看看力扣第 886 題「可能的二分法」：

函數(shù)簽名如下：

boolean?possibleBipartition(int?n,?int[][]?dislikes);

其實(shí)這題考察的就是二分圖的判定：

如果你把每個(gè)人看做圖中的節(jié)點(diǎn)，相互討厭的關(guān)系看做圖中的邊，那么dislikes數(shù)組就可以構(gòu)成一幅圖；

又因?yàn)轭}目說互相討厭的人不能放在同一組里，相當(dāng)于圖中的所有相鄰節(jié)點(diǎn)都要放進(jìn)兩個(gè)不同的組；

那就回到了「雙色問題」，如果能夠用兩種顏色著色所有節(jié)點(diǎn)，且相鄰節(jié)點(diǎn)顏色都不同，那么你按照顏色把這些節(jié)點(diǎn)分成兩組不就行了嘛。

所以解法就出來了，我們把dislikes構(gòu)造成一幅圖，然后執(zhí)行二分圖的判定算法即可：

private?boolean?ok?=?true; private?boolean[]?color; private?boolean[]?visited;public?boolean?possibleBipartition(int?n,?int[][]?dislikes)?{//?圖節(jié)點(diǎn)編號為?1...ncolor?=?new?boolean[n?+?1];visited?=?new?boolean[n?+?1];//?轉(zhuǎn)化成鄰接表表示圖結(jié)構(gòu)List<Integer>[]?graph?=?buildGraph(n,?dislikes);for?(int?v?=?1;?v?<=?n;?v++)?{if?(!visited[v])?{traverse(graph,?v);}}return?ok; }//?建圖函數(shù) private?List<Integer>[]?buildGraph(int?n,?int[][]?dislikes)?{//?圖節(jié)點(diǎn)編號為?1...nList<Integer>[]?graph?=?new?LinkedList[n?+?1];for?(int?i?=?1;?i?<=?n;?i++)?{graph[i]?=?new?LinkedList<>();}for?(int[]?edge?:?dislikes)?{int?v?=?edge[1];int?w?=?edge[0];//?「無向圖」相當(dāng)于「雙向圖」//?v?->?wgraph[v].add(w);//?w?->?vgraph[w].add(v);}return?graph; }//?和之前的?traverse?函數(shù)完全相同 private?void?traverse(List<Integer>[]?graph,?int?v)?{if?(!ok)?return;visited[v]?=?true;for?(int?w?:?graph[v])?{if?(!visited[w])?{color[w]?=?!color[v];traverse(graph,?w);}?else?{if?(color[w]?==?color[v])?{ok?=?false;}}} }

至此，這道題也使用 DFS 算法解決了，如果你想用 BFS 算法，和之前寫的解法是完全一樣的，可以自己嘗試實(shí)現(xiàn)。

二分圖的判定算法就講到這里，更多二分圖的高級算法，敬請期待。

最后，公眾號后臺回復(fù)「微信」可加我好友，回復(fù)「目錄」可獲取精選文章分類。關(guān)注我的視頻號，每周直播分享：

總結(jié)

以上是生活随笔為你收集整理的东哥带你刷图论第四期：二分图的判定的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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