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