1. 項(xiàng)目概述從“圖”開始重識(shí)數(shù)據(jù)結(jié)構(gòu)干了這么多年開發(fā)也帶過(guò)不少新人我發(fā)現(xiàn)一個(gè)挺有意思的現(xiàn)象很多人學(xué)數(shù)據(jù)結(jié)構(gòu)學(xué)到“圖”這里就卡殼了。鏈表、棧、隊(duì)列還能比劃比劃一到圖看著那些點(diǎn)和線還有一堆什么“鄰接矩陣”、“深度優(yōu)先”、“最短路徑”的術(shù)語(yǔ)直接就懵了。大家私下聊起來(lái)都覺得圖這東西太“虛”離寫業(yè)務(wù)代碼好像很遠(yuǎn)。但事實(shí)恰恰相反圖可能是我們?nèi)粘ｉ_發(fā)中“最實(shí)用”卻“最被忽視”的數(shù)據(jù)結(jié)構(gòu)。你以為只有社交網(wǎng)絡(luò)的好友關(guān)系、地圖導(dǎo)航才用得上圖那可就小看它了。從微服務(wù)間的調(diào)用鏈路依賴分析到電商平臺(tái)商品推薦背后的關(guān)聯(lián)規(guī)則挖掘甚至是你代碼里模塊的循環(huán)依賴檢測(cè)底層邏輯都藏著圖的影子?！皵?shù)據(jù)結(jié)構(gòu)——圖1很詳細(xì)”這個(gè)標(biāo)題看起來(lái)像是一章教科書目錄但它點(diǎn)出了學(xué)習(xí)圖的關(guān)鍵詳細(xì)。不詳細(xì)不行因?yàn)閳D的概念本身就是立體的、網(wǎng)狀的理解它需要從多個(gè)維度把它拆解清楚。今天我就以一個(gè)老碼農(nóng)的視角拋開那些刻板的定義帶大家重新“盤一盤”圖這個(gè)數(shù)據(jù)結(jié)構(gòu)。我們不求一口氣吃成胖子這第一篇就聚焦在最核心的“是什么”和“怎么存”這兩個(gè)問(wèn)題上。我會(huì)把那些書本上枯燥的定義換成我們開發(fā)中能碰到的實(shí)際場(chǎng)景再配上手把手的代碼實(shí)現(xiàn)這里主要以Python和Java為例因其表達(dá)清晰讓你不僅知道圖是“點(diǎn)”和“邊”更明白在不同的需求下為什么要選擇某種特定的存儲(chǔ)方式。這是你能否真正用好圖的第一步也是從“知道”到“會(huì)用”的關(guān)鍵跨越。2. 圖的核心概念與生活化映射在開始敲代碼之前我們必須把圖的基本家當(dāng)認(rèn)識(shí)清楚。這些概念是后續(xù)所有討論的基石但我保證我會(huì)用你最熟悉的東西來(lái)類比。2.1 頂點(diǎn)與邊世界的本質(zhì)是連接圖Graph由兩部分組成頂點(diǎn)Vertex和邊Edge。你可以把頂點(diǎn)想象成任何你感興趣的對(duì)象一個(gè)人、一座城市、一個(gè)網(wǎng)頁(yè)、一個(gè)微服務(wù)、一個(gè)函數(shù)。而邊就是這些對(duì)象之間的關(guān)系。頂點(diǎn)Vertex / Node也叫節(jié)點(diǎn)。它就是圖中的一個(gè)數(shù)據(jù)元素。比如在微信好友關(guān)系圖里每個(gè)微信用戶就是一個(gè)頂點(diǎn)。邊Edge連接兩個(gè)頂點(diǎn)的線表示它們之間存在某種關(guān)系。在好友關(guān)系里如果用戶A和用戶B是好友那就在他們之間畫一條邊。僅僅知道這兩樣還不夠邊還有不同的“性格”這直接決定了圖的類型和能解決的問(wèn)題。2.2 有向圖 vs. 無(wú)向圖關(guān)系的方向性這是圖的第一個(gè)重要分類取決于邊有沒(méi)有“箭頭”。無(wú)向圖Undirected Graph邊沒(méi)有方向。就像微信好友關(guān)系A(chǔ)是B的好友等同于B也是A的好友。這條邊是雙向的、對(duì)等的。在無(wú)向圖中邊通常用圓括號(hào)表示如邊(A, B)。生活場(chǎng)景地鐵線路圖不考慮單向行駛的話、局域網(wǎng)中設(shè)備的連接關(guān)系、合作作者關(guān)系圖。有向圖Directed Graph / Digraph邊有方向。就像微博的關(guān)注關(guān)系A(chǔ)關(guān)注了B但B不一定關(guān)注了A。這條邊是單向的有明確的起點(diǎn)弧尾和終點(diǎn)弧頭。在有向圖中邊通常用尖括號(hào)表示如邊A, B表示從A指向B。生活場(chǎng)景網(wǎng)頁(yè)的超鏈接從當(dāng)前頁(yè)鏈向目標(biāo)頁(yè)、任務(wù)調(diào)度中的依賴關(guān)系A(chǔ)任務(wù)完成才能開始B任務(wù)、資金流向圖。注意在代碼實(shí)現(xiàn)時(shí)無(wú)向圖通常可以看作一種特殊的有向圖即每條無(wú)向邊等價(jià)于兩條方向相反的有向邊。但這個(gè)認(rèn)知會(huì)影響存儲(chǔ)空間和算法效率需要根據(jù)實(shí)際情況選擇。2.3 權(quán)重的引入給關(guān)系加上度量很多時(shí)候關(guān)系不僅有方向還有“強(qiáng)度”或“成本”。這就是帶權(quán)圖Weighted Graph也叫網(wǎng)絡(luò)Network。權(quán)重Weight附加在邊上的一個(gè)數(shù)值。它可以代表距離、耗時(shí)、成本、流量、相關(guān)性強(qiáng)度等等。生活場(chǎng)景地圖導(dǎo)航邊的權(quán)重就是道路的實(shí)際距離或通行時(shí)間。社交網(wǎng)絡(luò)邊的權(quán)重可以是好友間的親密度指數(shù)。通信網(wǎng)絡(luò)邊的權(quán)重可以是帶寬或延遲。帶權(quán)圖使得圖模型能描述更復(fù)雜、更貼近現(xiàn)實(shí)的世界從而支撐起最短路徑、最小生成樹、最大流等高級(jí)算法。2.4 連通性世界的碎片與整體“連通”這個(gè)概念描述的是圖中頂點(diǎn)的可達(dá)性。連通圖Connected Graph在無(wú)向圖中如果任意兩個(gè)頂點(diǎn)之間都存在一條路徑可以經(jīng)過(guò)其他頂點(diǎn)那么這個(gè)圖就是連通圖。想象一個(gè)所有島嶼都有橋相連的群島。非連通圖反之如果存在至少兩個(gè)頂點(diǎn)間沒(méi)有路徑就是非連通圖。它由多個(gè)“連通分量”組成。強(qiáng)連通圖Strongly Connected Graph這是針對(duì)有向圖的概念。如果圖中任意兩個(gè)頂點(diǎn)雙向可達(dá)即從A能到B從B也能到A那么它就是強(qiáng)連通圖。理解連通性對(duì)于分析系統(tǒng)穩(wěn)定性、信息傳播范圍至關(guān)重要。例如分析一個(gè)微服務(wù)調(diào)用圖如果它不是強(qiáng)連通的意味著存在某些服務(wù)是純粹的“生產(chǎn)者”或“消費(fèi)者”這在設(shè)計(jì)容錯(cuò)和監(jiān)控時(shí)需要考慮。2.5 度衡量頂點(diǎn)的重要性一個(gè)頂點(diǎn)的“度”Degree是和它相關(guān)聯(lián)的邊的數(shù)目。無(wú)向圖中頂點(diǎn)的度就是連接它的邊的條數(shù)。比如在好友圖中一個(gè)人的度就是他的好友數(shù)量。有向圖中度細(xì)分為入度In-degree和出度Out-degree。入度指向該頂點(diǎn)的邊的數(shù)量。在微博關(guān)注圖中入度就是粉絲數(shù)。出度從該頂點(diǎn)指出的邊的數(shù)量。在微博關(guān)注圖中出度就是關(guān)注數(shù)。度是圖分析中最簡(jiǎn)單的中心性指標(biāo)能快速識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)如社交網(wǎng)絡(luò)中的大V、調(diào)用鏈中的核心服務(wù)。3. 圖的存儲(chǔ)結(jié)構(gòu)空間與時(shí)間的博弈概念清楚了接下來(lái)就是怎么在計(jì)算機(jī)里把它存下來(lái)。這是實(shí)戰(zhàn)的第一步不同的存儲(chǔ)結(jié)構(gòu)對(duì)后續(xù)算法的效率有決定性影響。主要就兩種鄰接矩陣和鄰接表。選擇哪一種是一場(chǎng)典型的“空間換時(shí)間”或“時(shí)間換空間”的博弈。3.1 鄰接矩陣簡(jiǎn)單粗暴的“表格法”鄰接矩陣Adjacency Matrix使用一個(gè)二維數(shù)組矩陣來(lái)表示圖中頂點(diǎn)間的相鄰關(guān)系。存儲(chǔ)方式對(duì)于一個(gè)有n個(gè)頂點(diǎn)的圖創(chuàng)建一個(gè)n x n的矩陣matrix。對(duì)于無(wú)向圖如果頂點(diǎn) i 和 j 之間有邊則matrix[i][j]和matrix[j][i]都置為1或邊的權(quán)重否則為0或一個(gè)特殊值如無(wú)窮大。對(duì)于有向圖如果存在一條從頂點(diǎn) i 指向頂點(diǎn) j 的邊則matrix[i][j]置為1或權(quán)重。代碼示例Python - 無(wú)向無(wú)權(quán)圖class GraphWithMatrix: def __init__(self, num_vertices): self.num_vertices num_vertices # 初始化一個(gè) n x n 的零矩陣 self.matrix [[0] * num_vertices for _ in range(num_vertices)] def add_edge(self, v1, v2): # 假設(shè)是無(wú)向圖添加邊 v1-v2 if 0 v1 self.num_vertices and 0 v2 self.num_vertices: self.matrix[v1][v2] 1 self.matrix[v2][v1] 1 # 因?yàn)槭菬o(wú)向圖對(duì)稱設(shè)置 def has_edge(self, v1, v2): return self.matrix[v1][v2] 1 def print_matrix(self): for row in self.matrix: print(row) # 使用示例 g GraphWithMatrix(5) g.add_edge(0, 1) g.add_edge(0, 4) g.add_edge(1, 3) g.print_matrix() # 輸出 # [0, 1, 0, 0, 1] # [1, 0, 0, 1, 0] # [0, 0, 0, 0, 0] # [0, 1, 0, 0, 0] # [1, 0, 0, 0, 0]優(yōu)點(diǎn)直觀易于理解圖的信息一目了然。查詢速度快判斷任意兩個(gè)頂點(diǎn)間是否有邊或者獲取邊的權(quán)重時(shí)間復(fù)雜度是 O(1)。直接數(shù)組下標(biāo)訪問(wèn)即可。方便計(jì)算對(duì)于某些基于矩陣運(yùn)算的圖算法如通過(guò)計(jì)算矩陣的冪來(lái)尋找路徑非常友好。缺點(diǎn)空間復(fù)雜度高需要 O(V2) 的空間V為頂點(diǎn)數(shù)。對(duì)于頂點(diǎn)很多但邊很少的“稀疏圖”空間浪費(fèi)極其嚴(yán)重。想象一個(gè)有一百萬(wàn)用戶但平均每人只有一百個(gè)好友的社交網(wǎng)絡(luò)矩陣?yán)飳?huì)有萬(wàn)億個(gè)元素其中絕大多數(shù)是0。添加/刪除頂點(diǎn)麻煩需要重新分配和復(fù)制整個(gè)矩陣成本高。適用場(chǎng)景適用于稠密圖邊數(shù)接近頂點(diǎn)數(shù)的平方或者對(duì)“某兩點(diǎn)間是否有邊”這類查詢性能要求極高的場(chǎng)景。在小規(guī)模圖或教學(xué)演示中也常用。3.2 鄰接表靈活高效的“鏈表法”鄰接表Adjacency List是更常用、更節(jié)省空間的存儲(chǔ)方式。它為圖中的每個(gè)頂點(diǎn)都維護(hù)一個(gè)列表鏈表、數(shù)組等用來(lái)存儲(chǔ)所有與它直接相連的頂點(diǎn)對(duì)于帶權(quán)圖則存儲(chǔ)頂點(diǎn)和權(quán)重的對(duì)。存儲(chǔ)方式使用一個(gè)數(shù)組或字典索引或鍵代表頂點(diǎn)。每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)列表存儲(chǔ)它的所有鄰接頂點(diǎn)信息。代碼示例Java - 有向帶權(quán)圖import java.util.*; class Edge { int target; // 目標(biāo)頂點(diǎn) int weight; // 邊權(quán)重 public Edge(int target, int weight) { this.target target; this.weight weight; } } class GraphWithList { private int numVertices; private LinkedListEdge[] adjList; // 鄰接表數(shù)組 public GraphWithList(int numVertices) { this.numVertices numVertices; adjList new LinkedList[numVertices]; for (int i 0; i numVertices; i) { adjList[i] new LinkedList(); } } // 添加一條有向邊 from - to權(quán)重為weight public void addDirectedEdge(int from, int to, int weight) { if (from 0 from numVertices to 0 to numVertices) { adjList[from].add(new Edge(to, weight)); } } // 添加一條無(wú)向邊 v1-v2權(quán)重為weight public void addUndirectedEdge(int v1, int v2, int weight) { addDirectedEdge(v1, v2, weight); addDirectedEdge(v2, v1, weight); } // 打印鄰接表 public void printGraph() { for (int i 0; i numVertices; i) { System.out.print(Vertex i - ); for (Edge edge : adjList[i]) { System.out.print(( edge.target , edge.weight ) ); } System.out.println(); } } } // 使用示例 public class Main { public static void main(String[] args) { GraphWithList g new GraphWithList(5); g.addDirectedEdge(0, 1, 5); g.addDirectedEdge(0, 4, 2); g.addUndirectedEdge(1, 3, 1); g.printGraph(); // 輸出類似 // Vertex 0 - (1, 5) (4, 2) // Vertex 1 - (3, 1) (0, 5) // 注意因?yàn)閍ddUndirectedEdge1也指向0 // Vertex 2 - // Vertex 3 - (1, 1) // Vertex 4 - (0, 2) } }優(yōu)點(diǎn)空間效率高空間復(fù)雜度為 O(V E)其中V是頂點(diǎn)數(shù)E是邊數(shù)。對(duì)于稀疏圖這比鄰接矩陣節(jié)省大量空間。添加頂點(diǎn)靈活動(dòng)態(tài)添加頂點(diǎn)相對(duì)容易尤其是在使用基于字典的鄰接表時(shí)。遍歷鄰接點(diǎn)高效要找到一個(gè)頂點(diǎn)的所有鄰居直接遍歷其列表即可非常高效。這是很多圖算法如BFS/DFS的基礎(chǔ)操作。缺點(diǎn)查詢邊效率較低判斷頂點(diǎn) i 和 j 之間是否有邊需要遍歷 i 的鄰接列表時(shí)間復(fù)雜度為 O(degree(i))在最壞情況下是 O(V)。比鄰接矩陣的 O(1) 慢。實(shí)現(xiàn)稍復(fù)雜需要管理多個(gè)鏈表或動(dòng)態(tài)數(shù)組。適用場(chǎng)景絕大多數(shù)實(shí)際應(yīng)用尤其是稀疏圖。社交網(wǎng)絡(luò)、路由拓?fù)?、文件依賴關(guān)系等幾乎都是稀疏圖因此鄰接表是事實(shí)上的標(biāo)準(zhǔn)選擇。3.3 存儲(chǔ)結(jié)構(gòu)的選擇心法怎么選記住下面這個(gè)簡(jiǎn)單的決策流圖稠密嗎邊數(shù)E接近V2 - 優(yōu)先考慮鄰接矩陣。查詢快且空間浪費(fèi)相對(duì)可接受。圖稀疏嗎邊數(shù)E遠(yuǎn)小于V2 - 毫不猶豫選擇鄰接表。省空間且大多數(shù)算法在鄰接表上運(yùn)行更快。核心操作是什么如果需要頻繁判斷任意兩點(diǎn)間是否有邊- 傾向于鄰接矩陣。如果需要頻繁遍歷某個(gè)頂點(diǎn)的所有鄰居絕大多數(shù)圖算法都是 - 傾向于鄰接表。頂點(diǎn)數(shù)量會(huì)動(dòng)態(tài)變化嗎- 鄰接表特別是基于哈希表的實(shí)現(xiàn)通常更靈活。實(shí)操心得在工程實(shí)踐中鄰接表的變種使用最多。比如對(duì)于頂點(diǎn)標(biāo)識(shí)不是連續(xù)整數(shù)的情況例如用用戶名、城市名做頂點(diǎn)我們會(huì)用HashMapString, ListEdge來(lái)存儲(chǔ)。對(duì)于追求極致遍歷性能的場(chǎng)景可能會(huì)用ListListEdge數(shù)組動(dòng)態(tài)數(shù)組因?yàn)檫B續(xù)內(nèi)存訪問(wèn)比鏈表更快。選擇時(shí)一定要結(jié)合你的數(shù)據(jù)規(guī)模和操作頻次來(lái)權(quán)衡。4. 基礎(chǔ)操作實(shí)現(xiàn)與復(fù)雜度分析理解了存儲(chǔ)結(jié)構(gòu)我們來(lái)看看基于這兩種結(jié)構(gòu)如何實(shí)現(xiàn)圖的基本操作并分析其時(shí)間復(fù)雜度。這是評(píng)估我們?cè)O(shè)計(jì)是否合理的關(guān)鍵。4.1 基于鄰接矩陣的操作我們以n個(gè)頂點(diǎn)的圖為例矩陣為M。操作具體描述代碼思路時(shí)間復(fù)雜度說(shuō)明判斷邊是否存在查詢頂點(diǎn)u到v是否有邊直接返回M[u][v]的值非0或特定值O(1)矩陣的最大優(yōu)勢(shì)所在添加邊在頂點(diǎn)u和v間添加一條邊無(wú)向設(shè)置M[u][v] M[v][u] weightO(1)直接賦值刪除邊刪除頂點(diǎn)u和v間的邊設(shè)置M[u][v] M[v][u] 0或無(wú)窮大O(1)直接賦值遍歷鄰居找出頂點(diǎn)v的所有鄰接頂點(diǎn)遍歷矩陣的第v行或第v列找出所有非零元素O(n)必須掃描整行即使鄰居很少添加頂點(diǎn)在圖中添加一個(gè)新頂點(diǎn)需要?jiǎng)?chuàng)建一個(gè)新的(n1) x (n1)的矩陣并將舊數(shù)據(jù)復(fù)制過(guò)去O(n2)成本非常高是矩陣的致命缺點(diǎn)之一可以看到鄰接矩陣在“查邊”、“改邊”上效率無(wú)敵但在“遍歷鄰居”和“增刪頂點(diǎn)”上表現(xiàn)不佳尤其是對(duì)于稀疏圖遍歷鄰居做了大量無(wú)用功。4.2 基于鄰接表的操作我們假設(shè)使用ListListEdge存儲(chǔ)共有V個(gè)頂點(diǎn)頂點(diǎn)v的度為deg(v)。操作具體描述代碼思路時(shí)間復(fù)雜度說(shuō)明判斷邊是否存在查詢頂點(diǎn)u到v是否有邊遍歷adjList[u]這個(gè)列表查找target v的邊O(deg(u))最壞情況需遍歷整個(gè)列表即 O(V)添加邊添加從u到v的邊在adjList[u]列表末尾添加一個(gè)新邊對(duì)象(v, weight)O(1)(平均)添加到鏈表/動(dòng)態(tài)數(shù)組末尾通常很快刪除邊刪除從u到v的邊遍歷adjList[u]列表找到并移除target v的邊O(deg(u))需要查找鏈表刪除為O(1)數(shù)組刪除需移位遍歷鄰居找出頂點(diǎn)v的所有鄰接頂點(diǎn)直接遍歷adjList[v]這個(gè)列表即可O(deg(v))極其高效只訪問(wèn)實(shí)際存在的邊添加頂點(diǎn)在圖中添加一個(gè)新頂點(diǎn)在adjList中添加一個(gè)新的空列表O(1)(平均)動(dòng)態(tài)數(shù)組擴(kuò)容有均攤成本但很低鄰接表的優(yōu)勢(shì)一目了然它完美適配了圖算法中最常見的操作——遍歷頂點(diǎn)的所有鄰居。對(duì)于稀疏圖deg(v)遠(yuǎn)小于V因此效率遠(yuǎn)高于鄰接矩陣。其弱點(diǎn)在于判斷任意邊是否存在較慢但幸運(yùn)的是大多數(shù)經(jīng)典圖算法如遍歷、最短路徑并不頻繁需要這個(gè)操作它們更多的是在遍歷鄰居。避坑技巧如果你真的在使用鄰接表時(shí)需要頻繁判斷邊是否存在可以考慮引入輔助數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化。例如在存儲(chǔ)鄰接表的同時(shí)維護(hù)一個(gè)HashSet或布爾矩陣來(lái)記錄邊是否存在用額外的空間來(lái)?yè)Q取 O(1) 的查詢時(shí)間。這又是一個(gè)典型的“空間換時(shí)間”策略需要根據(jù)具體場(chǎng)景權(quán)衡。5. 實(shí)戰(zhàn)從零構(gòu)建一個(gè)簡(jiǎn)單的圖類光說(shuō)不練假把式。讓我們用Python實(shí)現(xiàn)一個(gè)支持無(wú)向/有向、帶權(quán)/不帶權(quán)的通用圖類采用最實(shí)用的鄰接表存儲(chǔ)并實(shí)現(xiàn)一些基礎(chǔ)方法。from collections import deque import heapq class Graph: 一個(gè)基于鄰接表的通用圖類 def __init__(self, directedFalse): 初始化圖。 :param directed: 是否為有向圖默認(rèn)為無(wú)向圖。 self.adj_list {} # 字典頂點(diǎn) - 列表[(鄰居, 權(quán)重)] self.directed directed self.vertices set() # 存儲(chǔ)所有頂點(diǎn)便于遍歷 def add_vertex(self, vertex): 添加一個(gè)頂點(diǎn)。 if vertex not in self.adj_list: self.adj_list[vertex] [] self.vertices.add(vertex) def add_edge(self, v1, v2, weight1): 添加一條邊。 :param v1: 起點(diǎn)頂點(diǎn) :param v2: 終點(diǎn)頂點(diǎn) :param weight: 邊權(quán)重默認(rèn)為1無(wú)權(quán)圖 # 確保頂點(diǎn)存在 self.add_vertex(v1) self.add_vertex(v2) # 添加邊 v1 - v2 self.adj_list[v1].append((v2, weight)) # 如果是無(wú)向圖還需要添加邊 v2 - v1 if not self.directed: self.adj_list[v2].append((v1, weight)) def get_neighbors(self, vertex): 獲取一個(gè)頂點(diǎn)的所有鄰居及權(quán)重。 return self.adj_list.get(vertex, []) def get_vertices(self): 返回圖中所有頂點(diǎn)的列表。 return list(self.vertices) def has_edge(self, v1, v2): 判斷是否存在從v1到v2的邊。 if v1 not in self.adj_list: return False for neighbor, _ in self.adj_list[v1]: if neighbor v2: return True return False def bfs(self, start_vertex): 廣度優(yōu)先搜索返回遍歷順序。 visited set() queue deque([start_vertex]) result [] while queue: vertex queue.popleft() if vertex not in visited: visited.add(vertex) result.append(vertex) # 將未訪問(wèn)的鄰居加入隊(duì)列 for neighbor, _ in self.get_neighbors(vertex): if neighbor not in visited: queue.append(neighbor) return result def dfs(self, start_vertex): 深度優(yōu)先搜索遞歸版返回遍歷順序。 visited set() result [] def _dfs(vertex): visited.add(vertex) result.append(vertex) for neighbor, _ in self.get_neighbors(vertex): if neighbor not in visited: _dfs(neighbor) _dfs(start_vertex) return result # 使用示例 if __name__ __main__: print( 示例1構(gòu)建一個(gè)無(wú)向無(wú)權(quán)圖社交網(wǎng)絡(luò) ) social_graph Graph(directedFalse) social_graph.add_edge(Alice, Bob) social_graph.add_edge(Alice, Charlie) social_graph.add_edge(Bob, David) social_graph.add_edge(Charlie, David) print(Alice的好友:, [n for n, _ in social_graph.get_neighbors(Alice)]) print(Bob和David是好友嗎?, social_graph.has_edge(Bob, David)) print(從Alice開始的BFS遍歷:, social_graph.bfs(Alice)) print(從Alice開始的DFS遍歷:, social_graph.dfs(Alice)) print(\n 示例2構(gòu)建一個(gè)有向帶權(quán)圖交通網(wǎng)絡(luò) ) traffic_graph Graph(directedTrue) traffic_graph.add_edge(A市, B市, 100) # A到B距離100km traffic_graph.add_edge(A市, C市, 150) traffic_graph.add_edge(B市, C市, 80) traffic_graph.add_edge(C市, D市, 120) # 注意這是有向圖所以 D市 到 C市 沒(méi)有路 print(從A市可直達(dá)的城市:) for city, dist in traffic_graph.get_neighbors(A市): print(f - {city} ({dist}km)) print(從D市可直達(dá)的城市:, traffic_graph.get_neighbors(D市)) # 可能是空的 print(從A市開始的BFS遍歷按距離一層層擴(kuò)散:, traffic_graph.bfs(A市))這個(gè)Graph類雖然簡(jiǎn)單但骨架清晰涵蓋了核心操作。它使用字典來(lái)存儲(chǔ)鄰接表使得頂點(diǎn)可以是任意可哈希的類型字符串、數(shù)字、元組等非常靈活。BFS和DFS是圖遍歷的兩種最基本、最重要的算法是后續(xù)所有高級(jí)算法如最短路徑、連通分量分析的基石。6. 常見問(wèn)題與排查技巧實(shí)錄在實(shí)際實(shí)現(xiàn)和使用圖的過(guò)程中肯定會(huì)遇到各種坑。下面是我總結(jié)的一些典型問(wèn)題和解決思路。6.1 內(nèi)存溢出圖太大了怎么辦當(dāng)頂點(diǎn)和邊數(shù)量極大例如數(shù)億級(jí)別時(shí)即使用鄰接表內(nèi)存也可能吃不消。問(wèn)題現(xiàn)象程序在構(gòu)建圖或運(yùn)行算法時(shí)崩潰報(bào)MemoryError。排查與解決換用更緊湊的數(shù)據(jù)結(jié)構(gòu)如果頂點(diǎn)是連續(xù)的整數(shù)ID用ListListEdge代替HashMapInteger, ListEdge可以節(jié)省大量對(duì)象開銷和哈希表開銷。使用原始類型集合在Java中考慮使用fastutil、hppc或Eclipse Collections這類庫(kù)提供的原始類型集合如IntArrayList避免Integer對(duì)象的裝箱開銷?？紤]壓縮稀疏矩陣對(duì)于極度稀疏且需要矩陣運(yùn)算的圖可以研究CSRCompressed Sparse Row或CSC格式它們是存儲(chǔ)稀疏矩陣的標(biāo)準(zhǔn)工業(yè)格式。使用磁盤或分布式存儲(chǔ)單機(jī)內(nèi)存無(wú)法容納時(shí)必須考慮使用圖數(shù)據(jù)庫(kù)如Neo4j、JanusGraph或分布式圖計(jì)算框架如Spark GraphX、Giraph將圖和計(jì)算任務(wù)分布到多臺(tái)機(jī)器上。采樣或分區(qū)如果業(yè)務(wù)允許可以對(duì)圖進(jìn)行采樣分析子圖或分區(qū)分別處理圖的不同部分。6.2 遍歷陷入死循環(huán)圖中有環(huán)這是實(shí)現(xiàn)DFS時(shí)最容易犯的錯(cuò)誤尤其是在處理有向圖時(shí)。問(wèn)題現(xiàn)象遞歸版本的DFS導(dǎo)致RecursionError遞歸深度超限或棧溢出非遞歸版本則可能無(wú)限循環(huán)。根本原因圖中有環(huán)Cycle遍歷時(shí)重復(fù)訪問(wèn)了已訪問(wèn)過(guò)的頂點(diǎn)。解決方案必須維護(hù)一個(gè)visited集合記錄已經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。在訪問(wèn)任何一個(gè)頂點(diǎn)之前先檢查它是否在visited中。遞歸DFS如上面示例所示在遞歸函數(shù)入口檢查并標(biāo)記visited。非遞歸DFS棧在將頂點(diǎn)壓棧前檢查visited。BFS隊(duì)列同樣在將頂點(diǎn)入隊(duì)前檢查visited。注意對(duì)于有向無(wú)環(huán)圖DAG的拓?fù)渑判虻人惴╲isited的狀態(tài)可能需要更精細(xì)的管理如“未訪問(wèn)”、“訪問(wèn)中”、“已訪問(wèn)”三種狀態(tài)來(lái)檢測(cè)環(huán)。6.3 算法結(jié)果不對(duì)圖是有向還是無(wú)向這是一個(gè)非常低級(jí)的錯(cuò)誤但新手常犯。問(wèn)題現(xiàn)象比如你寫了一個(gè)尋找最短路徑的算法在無(wú)向圖上測(cè)試通過(guò)但用到自己的數(shù)據(jù)實(shí)際是有向圖上結(jié)果就錯(cuò)了。排查步驟首先確認(rèn)圖的類型你的數(shù)據(jù)模型本質(zhì)上是有向關(guān)系還是無(wú)向關(guān)系關(guān)注點(diǎn)、關(guān)注鏈、網(wǎng)頁(yè)鏈接是有向的好友關(guān)系、合作作者關(guān)系通常是無(wú)向的。檢查邊的添加邏輯在add_edge方法中是否根據(jù)directed標(biāo)志正確地添加了反向邊上面的示例代碼展示了正確的邏輯。可視化小規(guī)模測(cè)試圖用紙筆或繪圖工具如Graphviz畫出你構(gòu)建的小規(guī)模圖5-10個(gè)頂點(diǎn)手動(dòng)驗(yàn)證算法的正確性。這是調(diào)試圖算法最有效的方法之一。6.4 性能瓶頸遍歷鄰居太慢在鄰接表實(shí)現(xiàn)中遍歷鄰居本身是O(deg(v))很快。但如果這個(gè)操作被以極高的頻率調(diào)用或者deg(v)極大如網(wǎng)絡(luò)中的超級(jí)節(jié)點(diǎn)仍可能成為瓶頸。優(yōu)化思路使用更快的容器將ListEdge換成ArrayList在Java中或list在Python中利用CPU緩存局部性遍歷連續(xù)內(nèi)存比遍歷鏈表快得多。預(yù)計(jì)算或緩存如果某些頂點(diǎn)的鄰居列表在多次查詢中不變可以考慮緩存get_neighbors的結(jié)果。但要注意圖的動(dòng)態(tài)性如果圖會(huì)頻繁增刪邊緩存會(huì)失效。并行化如果算法允許可以對(duì)不同頂點(diǎn)的鄰居遍歷進(jìn)行并行處理。但需要注意線程安全和數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題?？紤]度分布如果圖中存在少數(shù)度極高的“超級(jí)節(jié)點(diǎn)”可能需要針對(duì)它們?cè)O(shè)計(jì)特殊的數(shù)據(jù)結(jié)構(gòu)或處理邏輯比如使用跳表Skip List或布隆過(guò)濾器Bloom Filter來(lái)快速判斷某個(gè)節(jié)點(diǎn)是否為其鄰居。6.5 如何調(diào)試復(fù)雜的圖算法圖算法狀態(tài)復(fù)雜單步調(diào)試往往眼花繚亂。我的調(diào)試三板斧小數(shù)據(jù)手算驗(yàn)證永遠(yuǎn)從一個(gè)只有3-5個(gè)頂點(diǎn)的小圖開始。在白紙上手動(dòng)運(yùn)行你的算法記錄每一步各個(gè)變量的狀態(tài)如距離數(shù)組、訪問(wèn)標(biāo)記、隊(duì)列內(nèi)容等再與程序輸出對(duì)比。打印關(guān)鍵狀態(tài)在算法關(guān)鍵步驟如每次從優(yōu)先隊(duì)列中取出節(jié)點(diǎn)時(shí)、每次松弛操作時(shí)打印出關(guān)鍵數(shù)據(jù)結(jié)構(gòu)的狀態(tài)。這比在調(diào)試器里看直觀得多?？梢暬虚g結(jié)果對(duì)于路徑查找類算法如Dijkstra可以輸出每一步的“當(dāng)前已知最短路徑”圖。有很多輕量級(jí)庫(kù)可以幫你把字典/列表結(jié)構(gòu)轉(zhuǎn)換成簡(jiǎn)單的DOT語(yǔ)言然后用Graphviz渲染成圖片。一圖勝千言。圖的第一部分我們從“是什么”聊到了“怎么存”并初步接觸了“怎么用”遍歷。這就像蓋房子地基和框架打好了后面砌墻裝修學(xué)習(xí)各種高級(jí)算法才能穩(wěn)固。最重要的是你現(xiàn)在應(yīng)該能清晰地回答面對(duì)一個(gè)實(shí)際問(wèn)題我該用有向圖還是無(wú)向圖該用鄰接矩陣還是鄰接表這個(gè)選擇比你后續(xù)寫什么算法都重要。在下一篇里我們會(huì)深入圖的遍歷不只是BFS和DFS的代碼更要講清楚它們?yōu)槭裁茨菢庸ぷ饕约叭绾斡盟鼈兘鉀Q像連通分量、環(huán)檢測(cè)、拓?fù)渑判蜻@樣的實(shí)際問(wèn)題。你會(huì)發(fā)現(xiàn)很多看似復(fù)雜的問(wèn)題其核心就是對(duì)圖的一次精心設(shè)計(jì)的遍歷。