1. 從迷宮到網(wǎng)絡(luò)圖論算法為何是程序員的必修課如果你玩過(guò)《塞爾達(dá)傳說(shuō)》或者任何一款迷宮游戲你肯定有過(guò)這樣的經(jīng)歷站在一個(gè)岔路口面前有三條路你需要決定走哪條才能最快找到寶箱或者出口。這個(gè)看似簡(jiǎn)單的“選擇”背后其實(shí)就隱藏著圖論算法的核心思想。在程序的世界里我們每天都在處理類(lèi)似的“迷宮”社交網(wǎng)絡(luò)里誰(shuí)是誰(shuí)的朋友社交圖譜、地圖軟件里如何規(guī)劃最短路徑導(dǎo)航算法、電商平臺(tái)如何給你推薦商品協(xié)同過(guò)濾、甚至編譯器如何優(yōu)化代碼的執(zhí)行順序控制流圖。這些看似風(fēng)馬牛不相及的問(wèn)題都可以抽象成“圖”這個(gè)數(shù)據(jù)結(jié)構(gòu)并用一套通用的算法工具來(lái)解決。今天我們不談枯燥的數(shù)學(xué)定義就從幾個(gè)你肯定遇到過(guò)或即將遇到的真實(shí)場(chǎng)景出發(fā)掰開(kāi)揉碎地講講那些支撐起現(xiàn)代數(shù)字世界的圖論相關(guān)算法。無(wú)論你是正在刷題準(zhǔn)備面試的新手還是需要解決實(shí)際工程問(wèn)題的老手掌握這些算法就相當(dāng)于獲得了一張解開(kāi)復(fù)雜系統(tǒng)關(guān)聯(lián)性的萬(wàn)能地圖。2. 圖的“靈魂”兩種存儲(chǔ)方式與你的選型困境在動(dòng)手寫(xiě)任何圖算法之前第一個(gè)攔路虎往往是如何把圖“裝”進(jìn)計(jì)算機(jī)里。這直接決定了后續(xù)所有操作的效率上限。主流有兩種方式鄰接矩陣和鄰接表。很多教程只告訴你“稀疏圖用鄰接表稠密圖用鄰接矩陣”但為什么以及在實(shí)際項(xiàng)目中到底怎么選這里面的門(mén)道可不少。2.1 鄰接矩陣直觀(guān)的“城市公交總圖”想象一個(gè)城市有N個(gè)公交站點(diǎn)鄰接矩陣就像一個(gè)巨大的N×N表格。表格的第i行第j列的值就表示從站點(diǎn)i到站點(diǎn)j有沒(méi)有直達(dá)公交車(chē)有權(quán)圖則是車(chē)費(fèi)或時(shí)間。用代碼表示就是一個(gè)二維數(shù)組matrix[i][j]。# 假設(shè)有5個(gè)頂點(diǎn)0-4構(gòu)建一個(gè)無(wú)向圖的鄰接矩陣 V 5 graph_matrix [[0] * V for _ in range(V)] # 添加邊0-1, 0-4, 1-2, 1-3, 1-4, 2-3, 3-4 edges [(0,1), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4)] for u, v in edges: graph_matrix[u][v] 1 graph_matrix[v][u] 1 # 無(wú)向圖需要對(duì)稱(chēng)設(shè)置 print(graph_matrix[0]) # 輸出頂點(diǎn)0的鄰居情況[0, 1, 0, 0, 1]它的優(yōu)勢(shì)極其明顯查詢(xún)速度極快判斷任意兩個(gè)頂點(diǎn)u和v是否直接相連即是否有邊只需要O(1)的時(shí)間訪(fǎng)問(wèn)matrix[u][v]。這在某些需要頻繁進(jìn)行“存在性檢查”的場(chǎng)景下是無(wú)可替代的。適合稠密圖當(dāng)圖的邊數(shù)量接近頂點(diǎn)數(shù)量的平方時(shí)即幾乎每個(gè)點(diǎn)都和其他點(diǎn)相連鄰接矩陣的空間利用率很高因?yàn)閹缀趺總€(gè)格子都被用上了。易于理解和實(shí)現(xiàn)結(jié)構(gòu)非常規(guī)整對(duì)于某些基于矩陣運(yùn)算的圖算法如通過(guò)矩陣乘法計(jì)算路徑有天然優(yōu)勢(shì)。但它的代價(jià)也同樣沉重空間消耗巨大空間復(fù)雜度是O(V^2)。對(duì)于一個(gè)有10000個(gè)頂點(diǎn)的社交網(wǎng)絡(luò)哪怕只有幾萬(wàn)個(gè)好友關(guān)系稀疏你也需要維護(hù)一個(gè)1億10000*10000大小的二維數(shù)組其中絕大部分都是0這是巨大的浪費(fèi)。添加/刪除頂點(diǎn)成本高動(dòng)態(tài)增加一個(gè)頂點(diǎn)需要重新分配并復(fù)制整個(gè)矩陣成本是O(V^2)。注意在面試或算法競(jìng)賽中如果題目明確頂點(diǎn)數(shù)V 500或1000鄰接矩陣通常是安全且編碼簡(jiǎn)單的選擇。但一旦V上萬(wàn)就要立刻警惕。2.2 鄰接表高效的“個(gè)人通訊錄”鄰接表則采用了完全不同的思路。它為每個(gè)頂點(diǎn)維護(hù)一個(gè)列表鏈表、動(dòng)態(tài)數(shù)組等這個(gè)列表里只存儲(chǔ)該頂點(diǎn)的直接鄰居。還是那個(gè)公交城市的例子現(xiàn)在你只擁有一本“個(gè)人通訊錄”記錄從你家某個(gè)頂點(diǎn)出發(fā)能坐哪幾路車(chē)分別到哪些鄰居家。from collections import defaultdict V 5 graph_adj_list defaultdict(list) # 使用字典存儲(chǔ)鍵為頂點(diǎn)值為鄰居列表 edges [(0,1), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4)] for u, v in edges: graph_adj_list[u].append(v) graph_adj_list[v].append(u) # 無(wú)向圖 print(graph_adj_list[0]) # 輸出頂點(diǎn)0的鄰居列表[1, 4] print(graph_adj_list[1]) # 輸出頂點(diǎn)1的鄰居列表[0, 2, 3, 4]鄰接表的優(yōu)勢(shì)在于空間效率高存儲(chǔ)空間為O(V E)其中E是邊數(shù)。對(duì)于稀疏圖E遠(yuǎn)小于V^2這比鄰接矩陣節(jié)省了海量?jī)?nèi)存。現(xiàn)代互聯(lián)網(wǎng)上的圖99%都是稀疏圖。遍歷鄰居高效要遍歷某個(gè)頂點(diǎn)的所有鄰居直接遍歷其列表即可時(shí)間復(fù)雜度是O(degree(v))其中degree(v)是該頂點(diǎn)的鄰居數(shù)。這對(duì)于BFS/DFS等需要遍歷邊的算法是最高效的。動(dòng)態(tài)增刪靈活添加邊和頂點(diǎn)相對(duì)容易。它的缺點(diǎn)則是查詢(xún)邊存在性慢判斷邊(u, v)是否存在需要遍歷u的鄰居列表最壞情況O(degree(u))。如果必須頻繁進(jìn)行此操作可能需要結(jié)合哈希集合來(lái)優(yōu)化。實(shí)現(xiàn)稍復(fù)雜相比矩陣的規(guī)整鄰接表的結(jié)構(gòu)更松散調(diào)試時(shí)直觀(guān)性稍差。2.3 實(shí)戰(zhàn)選型一個(gè)真實(shí)的踩坑案例我曾經(jīng)參與一個(gè)社交網(wǎng)絡(luò)“共同好友”功能的初期開(kāi)發(fā)。最初為了圖省事我用了鄰接矩陣因?yàn)榕袛唷癆和B是否是好友”這個(gè)操作太方便了。當(dāng)用戶(hù)量突破10萬(wàn)時(shí)服務(wù)內(nèi)存直接爆了。那個(gè)100000 x 100000的矩陣即使用boolean類(lèi)型1字節(jié)也輕松吃掉近100GB內(nèi)存而實(shí)際好友關(guān)系邊只有幾百萬(wàn)條。重構(gòu)方案我們換成了鄰接表每個(gè)用戶(hù)的ID作為鍵其好友ID列表作為值存儲(chǔ)在Redis的Hash結(jié)構(gòu)中。內(nèi)存驟降到幾百M(fèi)B。對(duì)于“判斷是否為好友”這個(gè)高頻操作我們?cè)诿總€(gè)用戶(hù)的好友列表外額外維護(hù)了一個(gè)Redis Set作為快速查詢(xún)的索引。雖然增加了一點(diǎn)寫(xiě)操作的成本需要同時(shí)更新列表和集合但換來(lái)了O(1)的查詢(xún)和O(VE)的內(nèi)存這是典型的“以空間換時(shí)間”策略在工程上的靈活變通。給你的建議在絕大多數(shù)應(yīng)用開(kāi)發(fā)中鄰接表是默認(rèn)且安全的選擇。除非你非常確定圖是稠密的或者頂點(diǎn)數(shù)極少且需要極快的隨機(jī)邊查詢(xún)。在算法題中根據(jù)頂點(diǎn)規(guī)模靈活選擇通常V 5000就該優(yōu)先考慮鄰接表。3. 圖的“探索”深度與廣度優(yōu)先搜索遠(yuǎn)不止遍歷那么簡(jiǎn)單DFS深度優(yōu)先搜索和BFS廣度優(yōu)先搜索是圖論算法世界的“原子操作”是幾乎所有高級(jí)算法的基礎(chǔ)。但很多人學(xué)了之后只記得“用棧”、“用隊(duì)列”卻不知道在什么場(chǎng)景下該用誰(shuí)以及如何利用它們解決實(shí)際問(wèn)題。3.1 DFS深入虎穴的探險(xiǎn)家與回溯算法DFS的策略是“一條路走到黑”就像走迷宮時(shí)遇到岔路口就隨便選一條路走下去直到死胡同再退回上一個(gè)岔路口選另一條路。它的遞歸結(jié)構(gòu)天然適合處理“探索所有可能路徑”的問(wèn)題。核心應(yīng)用場(chǎng)景連通分量計(jì)數(shù)判斷一個(gè)無(wú)向圖中有幾個(gè)互相不連通的“子圖”。這是很多社交網(wǎng)絡(luò)分析、圖像分割的底層原理。拓?fù)渑判蛴糜谟邢驘o(wú)環(huán)圖DAG解決任務(wù)調(diào)度、編譯順序等依賴(lài)問(wèn)題。DFS可以實(shí)現(xiàn)一個(gè)非常優(yōu)雅的拓?fù)渑判蛟谶f歸返回時(shí)將頂點(diǎn)入棧最后棧中序列就是逆拓?fù)湫?。檢測(cè)環(huán)尤其是在有向圖中通過(guò)DFS過(guò)程中標(biāo)記節(jié)點(diǎn)的狀態(tài)未訪(fǎng)問(wèn)、訪(fǎng)問(wèn)中、已訪(fǎng)問(wèn)可以高效檢測(cè)圖中是否存在環(huán)這是任務(wù)調(diào)度系統(tǒng)避免死鎖的關(guān)鍵?；厮菟惴ɑA(chǔ)諸如八皇后、數(shù)獨(dú)、全排列等問(wèn)題本質(zhì)上是在一個(gè)隱式的“狀態(tài)空間圖”上進(jìn)行DFS尋找滿(mǎn)足條件的路徑。DFS遞歸模板務(wù)必掌握visited set() # 記錄已訪(fǎng)問(wèn)節(jié)點(diǎn)避免重復(fù)訪(fǎng)問(wèn)和死循環(huán) def dfs(node): if node in visited: return # 處理當(dāng)前節(jié)點(diǎn) print(fVisiting {node}) visited.add(node) # 遍歷所有鄰居 for neighbor in graph_adj_list[node]: dfs(neighbor) # 對(duì)于非連通圖需要遍歷所有節(jié)點(diǎn)作為起點(diǎn) for node in range(V): if node not in visited: dfs(node)一個(gè)DFS的典型問(wèn)題尋找所有路徑。假設(shè)你要從一個(gè)城市到另一個(gè)城市想找出所有不重復(fù)城市的旅行方案。DFS非常適合因?yàn)樗鼤?huì)系統(tǒng)地探索每一條分支。def find_all_paths(graph, start, end, path[]): path path [start] # 創(chuàng)建當(dāng)前路徑的副本 if start end: return [path] # 找到一條完整路徑 if start not in graph: return [] paths [] for neighbor in graph[start]: if neighbor not in path: # 避免回路 new_paths find_all_paths(graph, neighbor, end, path) for p in new_paths: paths.append(p) return paths3.2 BFS層層推進(jìn)的雷達(dá)與最短路徑基石BFS的策略是“地毯式搜索”從起點(diǎn)開(kāi)始先訪(fǎng)問(wèn)所有直接鄰居再訪(fǎng)問(wèn)鄰居的鄰居以此類(lèi)推。它保證在無(wú)權(quán)圖中第一次訪(fǎng)問(wèn)到某個(gè)節(jié)點(diǎn)時(shí)走過(guò)的路徑就是最短路徑。核心應(yīng)用場(chǎng)景無(wú)權(quán)圖最短路徑這是BFS的招牌應(yīng)用。比如在社交網(wǎng)絡(luò)中計(jì)算“六度空間”兩個(gè)人之間最少通過(guò)多少人認(rèn)識(shí)或者在迷宮游戲中找最短出口路徑。層級(jí)遍歷或擴(kuò)散網(wǎng)絡(luò)爬蟲(chóng)按距離種子網(wǎng)址的“跳數(shù)”一層層抓取傳染病傳播模型模擬圖像填充算法。檢測(cè)二分圖通過(guò)BFS或DFS對(duì)節(jié)點(diǎn)進(jìn)行“染色”如果相鄰節(jié)點(diǎn)顏色沖突則不是二分圖。這在分配問(wèn)題、廣告投放匹配中有應(yīng)用。BFS隊(duì)列模板務(wù)必掌握f(shuō)rom collections import deque def bfs(start): visited set([start]) queue deque([start]) while queue: node queue.popleft() print(fProcessing {node}) # 處理當(dāng)前節(jié)點(diǎn) # 注意在這里node的層級(jí)就是它距離起點(diǎn)的最短距離無(wú)權(quán)圖 for neighbor in graph_adj_list[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)BFS找最短路徑長(zhǎng)度示例def shortest_path_length(graph, start, end): if start end: return 0 visited set([start]) queue deque([(start, 0)]) # (節(jié)點(diǎn), 距離) while queue: node, dist queue.popleft() for neighbor in graph[node]: if neighbor end: return dist 1 if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, dist 1)) return -1 # 不可達(dá)3.3 DFS vs BFS如何選擇一個(gè)決策框架很多新手會(huì)混淆。記住這個(gè)簡(jiǎn)單的決策鏈問(wèn)題是否要求“最短”或“最少步數(shù)”是- 優(yōu)先考慮BFS無(wú)權(quán)圖或Dijkstra有權(quán)圖。否- 進(jìn)入下一步。問(wèn)題是否需要遍歷或檢測(cè)圖中的“連通性”、“環(huán)”、“拓?fù)湫颉笔?DFS通常編碼更簡(jiǎn)潔。問(wèn)題是否需要“回溯”或“探索所有可能組合/排列”是- 這是DFS回溯的絕對(duì)領(lǐng)域。圖的結(jié)構(gòu)是否非常深分支少但路徑長(zhǎng)且可能答案在較淺層是- 使用BFS避免DFS陷入過(guò)深分支。反之如果圖很寬BFS隊(duì)列可能消耗大量?jī)?nèi)存DFS可能更合適。實(shí)操心得在解決具體問(wèn)題時(shí)我經(jīng)常先問(wèn)自己“我要找的是什么是一條可行解DFS常用于找解還是最優(yōu)解BFS常用于無(wú)權(quán)圖最優(yōu)” 同時(shí)考慮圖的規(guī)模。如果圖深度可能極大比如1萬(wàn)層遞歸DFS可能導(dǎo)致棧溢出需要顯式使用棧來(lái)實(shí)現(xiàn)迭代DFS。而B(niǎo)FS的空間復(fù)雜度在最壞情況下是O(V)在圖很寬時(shí)需要注意。4. 加權(quán)圖的“最優(yōu)解”Dijkstra與它的朋友們當(dāng)圖中的邊有了權(quán)重比如距離、時(shí)間、成本BFS就失效了因?yàn)樗J(rèn)每走一步代價(jià)相同。這時(shí)我們需要更強(qiáng)大的算法。Dijkstra算法是解決單源最短路徑問(wèn)題從一個(gè)點(diǎn)到圖中所有其他點(diǎn)的最短路徑最著名、最實(shí)用的算法。它的核心思想是“貪心”每次從未確定的節(jié)點(diǎn)中選擇一個(gè)距離起點(diǎn)最近的節(jié)點(diǎn)確認(rèn)它的最短距離并用它來(lái)更新其鄰居的距離。4.1 Dijkstra算法核心流程與手動(dòng)模擬我們用一個(gè)經(jīng)典例子來(lái)看求從頂點(diǎn)A到其他各點(diǎn)的最短距離。 假設(shè)圖如下鄰接表表示A - [(B, 1), (C, 4)] B - [(C, 2), (D, 6)] C - [(D, 3)] D - []步驟初始化起點(diǎn)A距離為0其他點(diǎn)距離為無(wú)窮大(∞)。所有點(diǎn)標(biāo)記為“未確定”。dist {A:0, B:∞, C:∞, D:∞}第一輪從未確定節(jié)點(diǎn){A(0), B(∞), C(∞), D(∞)}中選出距離最小的A(0)。確認(rèn)A的最短距離就是0。用A更新其鄰居B:min(∞, 01) 1C:min(∞, 04) 4dist {A:0, B:1, C:4, D:∞}第二輪未確定節(jié)點(diǎn){B(1), C(4), D(∞)}中最小是B(1)。確認(rèn)B的最短距離為1。用B更新鄰居C:min(4, 12) 3(發(fā)現(xiàn)經(jīng)過(guò)B到C更短)D:min(∞, 16) 7dist {A:0, B:1, C:3, D:7}第三輪未確定節(jié)點(diǎn){C(3), D(7)}中最小是C(3)。確認(rèn)C的最短距離為3。用C更新鄰居D:min(7, 33) 6dist {A:0, B:1, C:3, D:6}第四輪確認(rèn)最后一個(gè)未確定節(jié)點(diǎn)D(6)。算法結(jié)束。最終從A到各點(diǎn)的最短距離為A:0, B:1, C:3, D:6。4.2 優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)效率的關(guān)鍵上述手動(dòng)過(guò)程需要反復(fù)從集合中找最小值樸素實(shí)現(xiàn)是O(V^2)。工程上我們使用最小堆優(yōu)先級(jí)隊(duì)列來(lái)優(yōu)化這個(gè)“找最小”的過(guò)程可以將復(fù)雜度降至O((VE) log V)對(duì)于稀疏圖效率提升巨大。import heapq def dijkstra(graph, start): # 初始化距離字典所有點(diǎn)距離為無(wú)窮大 dist {node: float(inf) for node in graph} dist[start] 0 # 使用最小堆存儲(chǔ) (距離, 節(jié)點(diǎn)) pq [(0, start)] while pq: current_dist, current_node heapq.heappop(pq) # 如果當(dāng)前取出的距離大于已知最短距離說(shuō)明是舊數(shù)據(jù)跳過(guò) if current_dist dist[current_node]: continue # 遍歷鄰居 for neighbor, weight in graph[current_node]: distance current_dist weight # 如果找到更短的路徑 if distance dist[neighbor]: dist[neighbor] distance heapq.heappush(pq, (distance, neighbor)) return dist這段代碼有幾個(gè)關(guān)鍵點(diǎn)if current_dist dist[current_node]: continue這行是性能優(yōu)化的精髓。因?yàn)橥粋€(gè)節(jié)點(diǎn)可能被多次加入堆每次找到更短距離時(shí)但只有最早彈出即距離最小的那次是有效的后續(xù)彈出的都是“過(guò)時(shí)”的、更長(zhǎng)的距離直接跳過(guò)。使用(距離, 節(jié)點(diǎn))作為堆元素Python的heapq默認(rèn)按元組第一個(gè)元素排序正好符合需求。算法結(jié)束后dist字典就包含了從起點(diǎn)到所有可達(dá)節(jié)點(diǎn)的最短距離。4.3 Dijkstra的局限性負(fù)權(quán)邊與A*啟發(fā)式搜索Dijkstra算法有一個(gè)致命弱點(diǎn)無(wú)法處理含有負(fù)權(quán)邊的圖。為什么因?yàn)樗呢澬牟呗曰谝粋€(gè)假設(shè)“當(dāng)前距離最短的節(jié)點(diǎn)其最短距離已經(jīng)確定”。一旦存在負(fù)權(quán)邊這個(gè)假設(shè)就不成立了因?yàn)槲磥?lái)可能通過(guò)一條負(fù)權(quán)邊讓這個(gè)“已確定”節(jié)點(diǎn)的距離變得更短。對(duì)于帶負(fù)權(quán)邊的圖需要使用Bellman-Ford或SPFA算法。另一個(gè)常見(jiàn)變種是A*搜索算法。你可以把A理解為“帶導(dǎo)航的Dijkstra”。Dijkstra是盲目地向所有方向均勻探索而A則引入了一個(gè)啟發(fā)式函數(shù)h(n)用來(lái)估計(jì)從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的代價(jià)。優(yōu)先級(jí)隊(duì)列的排序依據(jù)從f(n) g(n)實(shí)際代價(jià)變成了f(n) g(n) h(n)實(shí)際估計(jì)。只要啟發(fā)函數(shù)h(n)是可采納的即永遠(yuǎn)不會(huì)高估實(shí)際代價(jià)A就能保證找到最短路徑并且通常比Dijkstra探索的節(jié)點(diǎn)少得多效率更高。地圖導(dǎo)航軟件就是A的典型應(yīng)用h(n)常選用兩點(diǎn)間的直線(xiàn)距離歐幾里得距離或曼哈頓距離。踩坑提醒實(shí)現(xiàn)Dijkstra時(shí)務(wù)必確保你的圖沒(méi)有負(fù)權(quán)邊。在業(yè)務(wù)中如果是計(jì)算物理距離、時(shí)間成本通常不會(huì)出現(xiàn)負(fù)數(shù)。但如果是計(jì)算利潤(rùn)、得分有正有負(fù)就需要換用其他算法。另外使用優(yōu)先級(jí)隊(duì)列時(shí)別忘了上面提到的“跳過(guò)舊數(shù)據(jù)”的判斷這是保證正確性和效率的關(guān)鍵。5. 最小生成樹(shù)用最少的線(xiàn)連接所有的點(diǎn)想象你要為一個(gè)新建小區(qū)的所有房屋鋪設(shè)光纖網(wǎng)絡(luò)要求所有房屋都能聯(lián)網(wǎng)連通并且使用的光纖總長(zhǎng)度最短。這就是最小生成樹(shù)Minimum Spanning Tree, MST的經(jīng)典問(wèn)題。它要在無(wú)向連通圖中找出一棵包含所有頂點(diǎn)的樹(shù)使得樹(shù)上所有邊的權(quán)重之和最小。5.1 Kruskal算法并查集的絕佳舞臺(tái)Kruskal算法的思想非常直觀(guān)從小到大考慮所有邊如果這條邊連接了兩個(gè)尚未連通的部件就選中它否則就跳過(guò)。這需要一種高效的數(shù)據(jù)結(jié)構(gòu)來(lái)判斷兩個(gè)頂點(diǎn)是否已經(jīng)連通——這就是并查集Union-Find。算法步驟將圖中所有邊按權(quán)重從小到大排序。初始化一個(gè)并查集每個(gè)頂點(diǎn)自成一個(gè)集合。按順序遍歷排序后的邊。對(duì)于每條邊(u, v, w)用并查集檢查u和v是否已經(jīng)在同一個(gè)集合中即已連通。如果不在則選中這條邊并將u和v所在的集合合并。如果已經(jīng)在則跳過(guò)避免形成環(huán)。當(dāng)選中邊的數(shù)量達(dá)到V-1條時(shí)一棵樹(shù)的邊數(shù)算法結(jié)束。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路徑壓縮 return self.parent[x] def union(self, x, y): rootX, rootY self.find(x), self.find(y) if rootX rootY: return False # 按秩合并 if self.rank[rootX] self.rank[rootY]: self.parent[rootX] rootY elif self.rank[rootX] self.rank[rootY]: self.parent[rootY] rootX else: self.parent[rootY] rootX self.rank[rootX] 1 return True def kruskal(n, edges): # edges: list of (weight, u, v) uf UnionFind(n) edges.sort() # 按權(quán)重排序 mst_weight 0 mst_edges [] for weight, u, v in edges: if uf.union(u, v): # 如果成功合并說(shuō)明邊被選中 mst_weight weight mst_edges.append((u, v, weight)) if len(mst_edges) n - 1: break return mst_weight, mst_edgesKruskal的適用場(chǎng)景非常適合邊比較稀疏的圖。因?yàn)樗臅r(shí)間復(fù)雜度主要取決于邊的排序O(E log E)后續(xù)的并查集操作接近常數(shù)時(shí)間。5.2 Prim算法從一點(diǎn)開(kāi)始生長(zhǎng)的貪心Prim算法的思路和Dijkstra很像但它生長(zhǎng)的是“一棵樹(shù)”而不是“最短路徑”。它從一個(gè)任意頂點(diǎn)開(kāi)始每次將連接當(dāng)前樹(shù)與樹(shù)外頂點(diǎn)的權(quán)重最小的邊以及該邊對(duì)應(yīng)的新頂點(diǎn)加入到樹(shù)中。算法步驟使用優(yōu)先級(jí)隊(duì)列優(yōu)化任選一個(gè)起始頂點(diǎn)將其加入最小生成樹(shù)集合MST_Set。將這個(gè)頂點(diǎn)的所有鄰接邊終點(diǎn)不在MST_Set中加入一個(gè)最小堆。循環(huán)直到MST_Set包含所有頂點(diǎn)從堆中彈出權(quán)重最小的邊(weight, u, v)其中u在MST_Set中v不在。將v加入MST_Set這條邊加入MST。將v的所有鄰接邊終點(diǎn)不在MST_Set中加入堆。注意和Dijkstra一樣同一條邊可能被多次加入堆需要判斷終點(diǎn)是否已在集合內(nèi)。import heapq def prim(n, graph): # graph: adjacency list, graph[u] [(v, weight), ...] visited [False] * n mst_weight 0 mst_edges [] # 從頂點(diǎn)0開(kāi)始 pq [] # (weight, u, v) visited[0] True for v, w in graph[0]: heapq.heappush(pq, (w, 0, v)) while pq and len(mst_edges) n - 1: weight, u, v heapq.heappop(pq) if visited[v]: continue # 跳過(guò)已訪(fǎng)問(wèn)的頂點(diǎn) visited[v] True mst_weight weight mst_edges.append((u, v, weight)) # 將新頂點(diǎn)v的邊加入堆 for next_v, next_w in graph[v]: if not visited[next_v]: heapq.heappush(pq, (next_w, v, next_v)) if len(mst_edges) ! n - 1: return None, None # 圖不連通無(wú)法生成MST return mst_weight, mst_edgesPrim的適用場(chǎng)景非常適合邊比較稠密的圖。它的時(shí)間復(fù)雜度為O(E log V)使用斐波那契堆可以?xún)?yōu)化到O(E V log V)但在競(jìng)賽和一般工程中優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)已經(jīng)足夠好。5.3 Kruskal vs Prim如何選擇這又是一個(gè)常見(jiàn)的選型問(wèn)題。我的經(jīng)驗(yàn)法則是看圖的稠密程度如果圖近乎完全圖邊數(shù)E ≈ V^2Prim算法尤其是鄰接矩陣實(shí)現(xiàn)更有優(yōu)勢(shì)。如果圖很稀疏E ≈ V或V log VKruskal算法更簡(jiǎn)潔高效?？磳?shí)現(xiàn)復(fù)雜度Kruskal需要寫(xiě)好并查集但一旦寫(xiě)好算法主體非常清晰。Prim需要維護(hù)一個(gè)不斷增長(zhǎng)的樹(shù)和堆邏輯稍復(fù)雜一點(diǎn)?？摧斎敫袷饺绻o你的就是邊的列表用Kruskal省去了建圖的步驟。如果給的是鄰接表或鄰接矩陣Prim可能更方便。實(shí)操心得在大多數(shù)編程競(jìng)賽中因?yàn)閳D通常以邊列表形式給出且不特別稠密所以Kruskal是更通用的選擇。但在實(shí)際工程項(xiàng)目中比如網(wǎng)絡(luò)布線(xiàn)、芯片設(shè)計(jì)圖的結(jié)構(gòu)可能更復(fù)雜需要根據(jù)具體情況分析。一個(gè)簡(jiǎn)單的記憶方法是“邊少用Kruskal邊多用Prim”。另外務(wù)必注意算法前提圖必須是無(wú)向連通圖。如果圖不連通得到的是“最小生成森林”。6. 拓?fù)渑判蚪忾_(kāi)任務(wù)依賴(lài)的死結(jié)當(dāng)你有一系列任務(wù)某些任務(wù)必須在另一些任務(wù)完成之后才能開(kāi)始比如編譯代碼時(shí)模塊A依賴(lài)模塊B就必須先編譯B你如何找到一個(gè)合理的執(zhí)行順序保證所有依賴(lài)都被滿(mǎn)足這就是拓?fù)渑判蛞鉀Q的問(wèn)題。它只適用于有向無(wú)環(huán)圖DAG。6.1 Kahn算法基于入度的廣度優(yōu)先策略Kahn算法非常直觀(guān)模擬了一個(gè)“不斷移除沒(méi)有前置依賴(lài)的任務(wù)”的過(guò)程。計(jì)算每個(gè)頂點(diǎn)的入度有多少條邊指向它。將所有入度為0的頂點(diǎn)加入一個(gè)隊(duì)列。當(dāng)隊(duì)列不為空時(shí)彈出隊(duì)首頂點(diǎn)u將其加入拓?fù)湫颉１闅vu的所有出邊(u - v)將v的入度減1。如果v的入度減為0則將v入隊(duì)。如果最終拓?fù)湫蛑械捻旤c(diǎn)數(shù)等于圖中總頂點(diǎn)數(shù)則排序成功否則說(shuō)明圖中存在環(huán)無(wú)法進(jìn)行拓?fù)渑判?。from collections import deque def topological_sort_kahn(graph, n): # graph: adjacency list, graph[u] [v, ...] 代表 u - v 的邊 in_degree [0] * n # 計(jì)算入度 for u in range(n): for v in graph[u]: in_degree[v] 1 queue deque([i for i in range(n) if in_degree[i] 0]) topo_order [] while queue: u queue.popleft() topo_order.append(u) for v in graph[u]: in_degree[v] - 1 if in_degree[v] 0: queue.append(v) if len(topo_order) n: return topo_order # 有效拓?fù)湫?else: return [] # 圖中有環(huán)Kahn算法的優(yōu)點(diǎn)容易理解便于檢測(cè)環(huán)。如果最后還有頂點(diǎn)入度不為0說(shuō)明這些頂點(diǎn)構(gòu)成了環(huán)的一部分。6.2 基于DFS的算法遞歸與后序的巧妙結(jié)合另一種方法利用DFS的遞歸特性。對(duì)一個(gè)頂點(diǎn)進(jìn)行DFS只有當(dāng)它的所有后繼節(jié)點(diǎn)都訪(fǎng)問(wèn)完成后才將其加入結(jié)果列表。最后將結(jié)果列表反轉(zhuǎn)即得到拓?fù)湫颉ef topological_sort_dfs(graph, n): visited [0] * n # 0未訪(fǎng)問(wèn), 1訪(fǎng)問(wèn)中, 2已訪(fǎng)問(wèn) topo_order [] def dfs(u): if visited[u] 1: # 遇到訪(fǎng)問(wèn)中的節(jié)點(diǎn)說(shuō)明有環(huán) return False if visited[u] 2: return True visited[u] 1 # 標(biāo)記為訪(fǎng)問(wèn)中 for v in graph[u]: if not dfs(v): return False visited[u] 2 # 標(biāo)記為已訪(fǎng)問(wèn) topo_order.append(u) # 在遞歸返回時(shí)加入順序是逆序的 return True for i in range(n): if visited[i] 0: if not dfs(i): return [] # 有環(huán) return topo_order[::-1] # 反轉(zhuǎn)得到拓?fù)湫駾FS方法的優(yōu)點(diǎn)代碼緊湊利用遞歸棧天然實(shí)現(xiàn)了“后序”處理。狀態(tài)數(shù)組visited用三種狀態(tài)巧妙地實(shí)現(xiàn)了環(huán)的檢測(cè)。6.3 拓?fù)渑判虻膽?yīng)用遠(yuǎn)不止任務(wù)調(diào)度課程安排LeetCode經(jīng)典題目“課程表”就是拓?fù)渑判虻闹苯討?yīng)用。構(gòu)建工具如Make, Maven, Gradle等確定源碼編譯順序。事件序列化在數(shù)據(jù)庫(kù)或分布式系統(tǒng)中確定具有依賴(lài)關(guān)系的事務(wù)的執(zhí)行順序。公式計(jì)算在電子表格中計(jì)算單元格公式時(shí)需要先計(jì)算被引用的單元格。依賴(lài)解析軟件包管理器如apt, yum, npm解決庫(kù)依賴(lài)關(guān)系。注意事項(xiàng)拓?fù)渑判虻慕Y(jié)果不唯一。一個(gè)DAG可能有多個(gè)合法的拓?fù)湫颉ahn算法和DFS算法產(chǎn)生的順序可能不同這取決于頂點(diǎn)處理的順序如隊(duì)列的初始順序、圖的存儲(chǔ)順序等。這在某些場(chǎng)景下很重要比如你希望任務(wù)盡可能并行執(zhí)行可能需要尋找一種特定的拓?fù)湫?。另外?wù)必在算法中加入環(huán)檢測(cè)因?yàn)楝F(xiàn)實(shí)中的數(shù)據(jù)可能包含循環(huán)依賴(lài)你的程序需要能優(yōu)雅地報(bào)告錯(cuò)誤而不是死循環(huán)或輸出錯(cuò)誤結(jié)果。