角跋蛐牵簲?shù)組模擬鄰接表的原理、實(shí)現(xiàn)與應(yīng)用)
鏈?zhǔn)角跋蛐沁@個(gè)名詞在很多初學(xué)者眼里屬于那種“聽說過但一直沒搞懂”的存在尤其是刷LeetCode、備戰(zhàn)算法競賽、考研數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)的時(shí)候總是繞不開它。我第一次接觸這個(gè)結(jié)構(gòu)是在做圖論題被vector鄰接表反復(fù)超時(shí)之后才真正下決心把它啃下來。這一篇我盡量把鏈?zhǔn)角跋蛐堑脑?、?shí)現(xiàn)、應(yīng)用和坑一次講清楚讓它成為你順手就能用的工具而不是只停留在收藏夾里的名詞。這個(gè)內(nèi)容適合誰正在準(zhǔn)備算法競賽的選手、考研或保研面試需要扎實(shí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的同學(xué)以及工作中需要用C/Java等語言實(shí)現(xiàn)高性能圖算法的人。鏈?zhǔn)角跋蛐墙鉀Q的核心問題其實(shí)很簡單在稀疏圖中如何用內(nèi)存更緊湊、常數(shù)更小的方式存儲圖的鄰接關(guān)系同時(shí)保證遍歷鄰接邊的高效。它本質(zhì)上是一種用數(shù)組模擬鏈表實(shí)現(xiàn)鄰接表的方法但比vector套vector的實(shí)現(xiàn)更可控比鄰接矩陣內(nèi)存占用小得多在網(wǎng)絡(luò)流、最短路、樹形DP等場景里都有非常廣泛的應(yīng)用。1. 鏈?zhǔn)角跋蛐堑谋举|(zhì)用數(shù)組模擬“帶索引的鄰接鏈表”1.1 從圖的存儲需求說起先想想我們存儲一張有向圖或無向圖時(shí)到底需要什么對每個(gè)頂點(diǎn)u要知道它和哪些頂點(diǎn)相連以及每條邊的權(quán)重如果有的話。最簡單的鄰接矩陣用一個(gè)n乘n的二維數(shù)組存查詢兩個(gè)點(diǎn)是否有邊是O(1)但空間是O(n^2)。當(dāng)n達(dá)到10^5邊數(shù)只有2*10^5時(shí)鄰接矩陣就是災(zāi)難光初始化一個(gè)10^5乘10^5的二維數(shù)組就夠你內(nèi)存爆掉。于是大家自然轉(zhuǎn)向鄰接表對每個(gè)頂點(diǎn)u維護(hù)一個(gè)列表里面存從u出發(fā)的所有邊。這個(gè)列表在C里最容易想到的實(shí)現(xiàn)就是vector adj[N]需要存權(quán)重時(shí)再用vectorpairint,int或者定義結(jié)構(gòu)體。vector實(shí)現(xiàn)簡單、思維負(fù)擔(dān)小所以很多人入門圖論時(shí)都用它?？蓡栴}在于vector不是為高頻插入和遍歷而生的每次push_back可能觸發(fā)內(nèi)存重新分配涉及拷貝和搬移遍歷時(shí)雖然是連續(xù)的但多個(gè)vector分布在不同內(nèi)存塊里整體緩存命中率不一定好。鏈?zhǔn)角跋蛐亲龅氖虑榫褪前选懊總€(gè)頂點(diǎn)的鄰接邊列表”用一條邏輯上的鏈表串起來而且整條鏈表的所有結(jié)點(diǎn)都放在幾個(gè)全局?jǐn)?shù)組里。它不依賴動態(tài)分配不依賴vector的實(shí)現(xiàn)細(xì)節(jié)而是自己管理“下一個(gè)結(jié)點(diǎn)是誰”。理解它之后你會發(fā)現(xiàn)它其實(shí)就是手寫了一個(gè)非常輕量的鄰接表。1.2 鏈?zhǔn)角跋蛐堑娜齻€(gè)核心數(shù)組鏈?zhǔn)角跋蛐峭ǔ＞S護(hù)三個(gè)數(shù)組或再加一個(gè)權(quán)重?cái)?shù)組head[u]表示從頂點(diǎn)u出發(fā)的第一條邊在邊數(shù)組中的下標(biāo)也可以理解為鏈表頭指針。to[i]第i條邊指向的終點(diǎn)頂點(diǎn)。nxt[i]第i條邊的下一條邊在下標(biāo)數(shù)組中的位置即鏈表的后繼指針。w[i]第i條邊的權(quán)值若需要。這里數(shù)組的下標(biāo)i是邊的編號每條邊的編號在添加時(shí)被確定。添加一條邊時(shí)采用頭插法新的邊結(jié)點(diǎn)插入到頂點(diǎn)u的鏈表頭部。也就是說void addEdge(int u, int v, int w) { to[cnt] v; // 邊的終點(diǎn) weight[cnt] w; // 邊的權(quán)值 nxt[cnt] head[u]; // 新邊的下一條邊指向原來u的第一條邊 head[u] cnt; // 更新u的鏈表頭為新邊 }看到這個(gè)操作是不是覺得特別像單鏈表的頭插法對它就是單鏈表。區(qū)別在于普通單鏈表的結(jié)點(diǎn)是動態(tài)new出來的要用指針連接鏈?zhǔn)角跋蛐怯脭?shù)組下標(biāo)指向下一個(gè)結(jié)點(diǎn)所以它的“指針”是一個(gè)int。這也是為什么它常被稱為“靜態(tài)鄰接表”。用一個(gè)生活化的類比來理解假設(shè)每個(gè)頂點(diǎn)是一個(gè)抽屜head[u]是抽屜里放的那張索引卡片卡片上寫著“第一條邊的編號”。每條邊的信息終點(diǎn)、權(quán)值、下一條邊的編號登記在賬本的某一行。頭插法相當(dāng)于每次來了新信息先在賬本上記一行然后更新抽屜里的卡片讓卡片指向最新一行同時(shí)在新一行里寫上“上一行是哪一行”。這樣從任一條邊出發(fā)都能沿著“下一條邊”的指引把整個(gè)抽屜里的邊全部翻出來。1.3 為什么它能提升性能連續(xù)性與可控性鏈?zhǔn)角跋蛐堑暮诵膬?yōu)勢之一是所有邊都存放在連續(xù)的數(shù)組里。用vector存鄰接表時(shí)雖然單個(gè)頂點(diǎn)的邊是連續(xù)存儲的但不同頂點(diǎn)的邊分散在不同vector中而鏈?zhǔn)角扒靶前阉羞吔y(tǒng)一放在幾個(gè)數(shù)組里更像是一塊連續(xù)的內(nèi)存被不同鏈表分塊占用。對CPU緩存來說連續(xù)數(shù)組的遍歷比其他零散分配的對象友好很多尤其當(dāng)你的算法需要反復(fù)遍歷某個(gè)頂點(diǎn)的所有鄰邊時(shí)這種友好會被放大。另一層優(yōu)勢是“可控”。vector的擴(kuò)容時(shí)機(jī)由標(biāo)準(zhǔn)庫決定在競賽這種對時(shí)間極其敏感的場景里你不知道某次push_back會觸發(fā)多大代價(jià)的重新分配。鏈?zhǔn)角跋蛐莿t不同只要你提前算好最大邊數(shù)開一個(gè)定長數(shù)組就完全避免動態(tài)分配所有內(nèi)存一次到位。再加上它的“指針”只是int下標(biāo)比64位指針小一半同樣存10萬條邊存儲開銷更低。這些優(yōu)勢疊加起來在圖規(guī)模比較大、算法常數(shù)要求高的題里可能就是壓線通過和超時(shí)的區(qū)別。2. 核心實(shí)現(xiàn)與每一步的原理拆解2.1 一張圖看懂添加和遍歷先看一個(gè)具體例子我們手動模擬一下向圖中添加幾條邊的過程這樣可以建立非常直觀的印象。假設(shè)有一張有向圖頂點(diǎn)1到22到31到3的邊按這個(gè)順序添加。初始時(shí)head[1]-1head[2]-1head[3]-1cnt0這里我用-1表示空鏈表。添加邊1-2cnt變成1to[1]2nxt[1]head[1]-1head[1]1。這時(shí)的鏈表狀態(tài)head[1]指向邊1邊1的next為-1。添加邊2-3cnt變成2to[2]3nxt[2]head[2]-1head[2]2。添加邊1-3cnt變成3to[3]3nxt[3]head[1]1head[1]3?，F(xiàn)在如果遍歷頂點(diǎn)1的所有出邊i head[1] 3訪問to[3]3這條路i nxt[3] 1訪問to[1]2這條路i nxt[1] -1遍歷結(jié)束?？吹?jīng)]有遍歷順序是倒過來的先添加的邊1-2反而后被訪問到。這是頭插法的天然特性大多數(shù)情況下順序不影響正確性但如果你依賴邊的訪問順序要記得這一點(diǎn)。這也是很多新手寫代碼時(shí)一時(shí)反應(yīng)不過來的地方。遍歷代碼很簡單for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; // 當(dāng)前邊指向的頂點(diǎn) int w weight[i]; // 當(dāng)前邊的權(quán)重 // 在這里處理業(yè)務(wù)邏輯 }這段代碼非?！皺C(jī)械”可以說是鏈?zhǔn)角跋蛐堑墓潭▽懛ū诚聛砭托?。關(guān)鍵是要理解為什么i nxt[i]能走到下一條邊以及為什么循環(huán)停止條件是i -1。2.2 頭插法與數(shù)組下標(biāo)管理細(xì)則添加邊的函數(shù)里有一個(gè)極其關(guān)鍵的細(xì)節(jié)cnt到底從0開始還是從1開始以及用cnt還是cnt這直接影響后面很多問題的處理。我習(xí)慣用以下的寫法const int N 100005; const int M 2 * 200005; // 無向圖注意開兩倍邊數(shù) int head[N], to[M], nxt[M], weight[M]; int cnt 0; inline void add(int u, int v, int w) { to[cnt] v; weight[cnt] w; nxt[cnt] head[u]; head[u] cnt; }這里cnt從0開始每次先再使用所以邊的編號從1開始。這樣有一個(gè)隱藏好處如果某道題里你在某個(gè)數(shù)組位置存了一個(gè)哨兵值0號位置不會被實(shí)際邊占用便于記憶和檢查。當(dāng)然也可以讓cnt從0開始使用0號位置這樣編號從0開始不過程序員之間的習(xí)慣差異很大重要的是你選一種并堅(jiān)持一致。初始化時(shí)head數(shù)組全部置為-1memset(head, -1, sizeof(head));有人會問為什么不用0表示空鏈表用0也行但需要把cnt初始化為0且add時(shí)用cnt而不是cnt并且還要額外設(shè)置0號位置的值。如果你用-1表示空代碼里所有遍歷的結(jié)束條件都寫成i ! -1語義非常明確。我建議新手一開始就用-1減少邊界條件混亂。2.3 有向圖、無向圖和反向邊問題鏈?zhǔn)角跋蛐翘幚碛邢驁D就是直接add(u, v, w)就完事。無向圖則要添加兩次add(u, v, w)和add(v, u, w)分別表示兩條方向相反的邊。這里有一個(gè)很多競賽選手愛用的經(jīng)典技巧如果添加無向邊時(shí)先add(u,v,w)再add(v,u,w)那么這兩條邊的編號分別為cnt1和cnt2并且滿足關(guān)系1號邊和2號邊互為反向邊3號邊和4號邊互為反向邊……更一般地說編號i和i^1是互為反向邊。這個(gè)性質(zhì)在處理網(wǎng)絡(luò)流算法時(shí)需要快速找反向邊極其有用。void addUndirected(int u, int v, int w) { add(u, v, w); add(v, u, w); } // 若需要訪問某條邊i的反向邊直接訪問 i ^ 1 即可這個(gè)“異或1”的技巧是鏈?zhǔn)角跋蛐窃诰W(wǎng)絡(luò)流題里的殺手锏之一。用vector鄰接表時(shí)你得在結(jié)構(gòu)體里存rev字段或者費(fèi)勁維護(hù)反向邊的位置而鏈?zhǔn)角跋蛐翘烊痪邆溥@個(gè)性質(zhì)。所以如果你準(zhǔn)備學(xué)Dinic、SAP這類算法鏈?zhǔn)角跋蛐菐缀跏潜貙W(xué)的前置內(nèi)容。3. 鏈?zhǔn)角跋蛐桥c主流存圖方式的橫向?qū)Ρ?.1 三種存圖方式的核心參數(shù)對比為了更直觀地看出區(qū)別我平時(shí)做題時(shí)會用這個(gè)表來做決策存儲方式空間復(fù)雜度判斷兩點(diǎn)是否相鄰遍歷某頂點(diǎn)所有鄰邊適用場景鄰接矩陣O(n^2)O(1)O(n)n很小通常1000以內(nèi)需要考慮稠密圖、需要頻繁判斷兩點(diǎn)是否相鄰vector鄰接表O(nm)需要遍歷列表最壞O(deg)O(deg)常數(shù)較大常規(guī)圖論題、實(shí)現(xiàn)簡單對性能不極致要求鏈?zhǔn)角跋蛐荗(nm)常數(shù)小需要遍歷列表同左O(deg)常數(shù)小數(shù)組連續(xù)大規(guī)模稀疏圖、網(wǎng)絡(luò)流、對時(shí)間和內(nèi)存限制嚴(yán)格的競賽題從工程上的直觀體感來說n10^5、m2*10^5級別的時(shí)候鏈?zhǔn)角跋蛐潜闅v鄰接邊的總時(shí)間大概是vector鄰接表的60%-80%。這個(gè)數(shù)字取決于編譯器和系統(tǒng)環(huán)境但趨勢是一致的。如果你的題目里需要跑很多輪遍歷比如反復(fù)做多源BFS、Dijkstra堆優(yōu)化里的多次松弛差距會被拉得更大。3.2 為什么說鏈?zhǔn)角跋蛐歉m合競賽和高性能場景很多人覺得既然有了vector為什么還要背鏈?zhǔn)角跋蛐菃栴}在于vector本質(zhì)是動態(tài)數(shù)組每次push_back遇到容量不夠時(shí)會重新分配內(nèi)存把舊內(nèi)容搬到新內(nèi)存里。這個(gè)過程雖然是均攤O(1)但單次操作可能突然變慢而且分配器本身也有開銷。在競賽評測機(jī)那種極端場景下有的題目就卡在這種常數(shù)上。而鏈?zhǔn)角跋蛐鞘恰笆止れo態(tài)分配”。你知道最多有多少條邊就把數(shù)組開夠。添加邊只是幾次數(shù)組賦值連內(nèi)存分配都沒有。同時(shí)因?yàn)樗羞叾荚谕粋€(gè)數(shù)組里遍歷的緩存局部性更好尤其當(dāng)你只需要訪問邊的終點(diǎn)、權(quán)值、下一條邊這三個(gè)字段時(shí)CPU可以把整塊數(shù)組搬到高速緩存里效率遠(yuǎn)高于分散在堆上的vector結(jié)點(diǎn)。這有點(diǎn)類似數(shù)據(jù)庫里“聚集索引”和“分散索引”的區(qū)別數(shù)據(jù)如果能物理連續(xù)地放在一起范圍掃描就會快很多。鏈?zhǔn)角跋蛐前堰叺慕Y(jié)構(gòu)天然聚集在同一片連續(xù)內(nèi)存里所以它跑掃描式的圖算法遍歷每個(gè)點(diǎn)的鄰邊確實(shí)有物理層面的優(yōu)勢。3.3 什么情況下不要執(zhí)念鏈?zhǔn)角跋蛐擎準(zhǔn)角跋蛐遣⒎侨f能。如果你的圖規(guī)模不大比如n在1000以內(nèi)或者你用的是Python、Java這類語言鏈?zhǔn)角跋蛐堑膬?yōu)勢會被語言本身的數(shù)組對象開銷稀釋。Python里你寫list套list反而更直觀而且Python的列表對象和循環(huán)開銷本身就是瓶頸手寫數(shù)組模擬并不能從根本上改變復(fù)雜度。再比如需要頻繁刪邊的場景鏈?zhǔn)角跋蛐亲觥拔锢韯h除”很麻煩。雖然你可以加一個(gè)vis標(biāo)記打懶標(biāo)記但如果你真的需要不斷地刪除某條邊、恢復(fù)某條邊動態(tài)鏈表或者平衡樹結(jié)構(gòu)會更合適。鏈?zhǔn)角跋蛐沁m合“建圖之后反復(fù)讀邊幾乎不做結(jié)構(gòu)修改”的場景這恰好覆蓋了絕大多數(shù)圖論算法題。4. 鏈?zhǔn)角跋蛐窃诮?jīng)典算法中的應(yīng)用4.1 堆優(yōu)化Dijkstra中的鏈?zhǔn)角跋蛐亲疃搪匪惴ɡ镦準(zhǔn)角跋蛐鞘嵌褍?yōu)化Dijkstra的固定搭檔。原因在于Dijkstra的核心操作是從優(yōu)先隊(duì)列里取出距離最小的點(diǎn)然后遍歷這個(gè)點(diǎn)的所有出邊嘗試松弛。這個(gè)過程對鄰接表的“遍歷”需求極其頻繁每一條出邊都要被訪問一次。用鏈?zhǔn)角跋蛐菍懗鰜矸浅Ｗ匀籿oid dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; int w weight[i]; if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }這段代碼里遍歷部分就是鏈?zhǔn)角跋蛐堑臉?biāo)準(zhǔn)循環(huán)沒有顯式的“遍歷索引”也沒有復(fù)雜的迭代器就三個(gè)數(shù)組三個(gè)變量清爽干凈。先把dist初始化成無窮大用0x3f可以避免加法溢出每次取出當(dāng)前最小點(diǎn)如果堆里的距離不是最新的就跳過這就是“惰性刪除”策略。4.2 DFS、BFS與樹DP的配套寫法DFS和BFS同樣可以直接套鏈?zhǔn)角跋蛐?。DFS的遞歸寫法void dfs(int u, int fa) { for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; if (v fa) continue; // 處理從u到v的邊 dfs(v, u); } }樹形DP時(shí)這個(gè)dfs里經(jīng)常要結(jié)合子樹信息做狀態(tài)轉(zhuǎn)移。比如求樹的重心、樹的直徑、子樹大小之類的問題鏈?zhǔn)角跋蛐潜闅v子節(jié)點(diǎn)非常合適。因?yàn)槊總€(gè)節(jié)點(diǎn)出邊的順序并不重要而鏈?zhǔn)酱鎯κ沟脧母腹?jié)點(diǎn)到子節(jié)點(diǎn)的跳躍只依賴一次數(shù)組下標(biāo)訪問。BFS的寫法也很直接用一個(gè)隊(duì)列存頂點(diǎn)每次彈出一個(gè)u就遍歷head[u]開頭的鏈表將所有未訪問的v入隊(duì)。整個(gè)過程中不需要像鄰接矩陣那樣對無關(guān)頂點(diǎn)也掃描一遍所以復(fù)雜度是O(nm)。4.3 網(wǎng)絡(luò)流算法中的反向邊利器網(wǎng)絡(luò)流算法Edmonds-Karp、Dinic、ISAP都需要維護(hù)殘量網(wǎng)絡(luò)核心操作之一就是不斷找到一條增廣路后對路徑上的邊的容量做減法并對反向邊容量做加法。這時(shí)前面提到的i^1技巧派上了用場你只要把邊從1開始編號保證每加入一條正向邊后立刻加入它的反向邊那么正向邊和反向邊的編號就是相鄰的異或1就能互相找到。我自己寫Dinic時(shí)一條addEdge函數(shù)inline void addEdge(int u, int v, int c) { to[cnt] v; cap[cnt] c; nxt[cnt] head[u]; head[u] cnt; to[cnt] u; cap[cnt] 0; nxt[cnt] head[v]; head[v] cnt; }正向邊容量c反向邊容量0。更新時(shí)int cur i ^ 1; cap[i] - flow; cap[cur] flow;這樣寫比vector版本清爽很多因?yàn)関ector需要你手動記錄反向邊在哪個(gè)位置甚至需要在結(jié)構(gòu)體里維護(hù)一個(gè)int rev。鏈?zhǔn)角跋蛐翘焐逊聪蜻吔壎ㄔ诰幪柈惢蜿P(guān)系上不用額外存儲自然成為圖論競賽選手網(wǎng)絡(luò)流題的首選。5. 常見問題與排查手把手解決鏈?zhǔn)角跋蛐堑目?.1 數(shù)組越界無向圖邊的數(shù)量要乘2這是我見過最多新手踩的坑。題目說m條無向邊你開數(shù)組時(shí)如果只開m大小那add兩次的時(shí)候第m1次添加就會越界。正確做法是至少開2m為了保險(xiǎn)我通常開2m5。有人可能會問為什么不是m5因?yàn)闊o向邊會拆成兩條有向邊存儲所以添加次數(shù)是2m。如果你開了m5的大小可能在本地測試小數(shù)據(jù)時(shí)一切正常一到大數(shù)據(jù)就直接RE運(yùn)行時(shí)錯(cuò)誤或者本地跑得慢提交上去返回段錯(cuò)誤。排查方法很簡單先檢查你的全局?jǐn)?shù)組大小是不是除以2了。5.2 head數(shù)組初始化為-1 vs 0和判重沖突鏈?zhǔn)角跋蛐堑呐袛鄺l件是i ! -1所以head初始化為-1非常關(guān)鍵。如果忘了初始化head里的值可能是0或者垃圾值導(dǎo)致遍歷時(shí)從錯(cuò)誤的邊開始甚至訪問到未定義的數(shù)組位置。多組測試數(shù)據(jù)時(shí)記得在每組數(shù)據(jù)開始前把head重新memset為-1。另外如果你使用0號邊作為哨兵那么head初始化為0并且add時(shí)用cnt先用0號位置再自增那么遍歷條件是i ! 0。這種寫法也可以但新手容易在調(diào)試時(shí)把0和-1搞混。我自己的建議是統(tǒng)一用-1別混用。5.3 遍歷順序相反導(dǎo)致結(jié)果不對鏈?zhǔn)角跋蛐鞘穷^插法所以邊的遍歷順序和添加順序相反。如果你在算法里依賴“先訪問到某條邊”的順序就很容易出bug。比如有些DP題需要按輸入的邊順序處理有些題需要你按特定順序輸出路徑這時(shí)別慌可以通過調(diào)整添加順序或者翻轉(zhuǎn)邏輯來修正。有個(gè)小技巧如果你希望遍歷順序和輸入順序一致可以在add的時(shí)候插入到鏈尾而不是鏈頭也就是維護(hù)一個(gè)tail數(shù)組記錄每個(gè)點(diǎn)當(dāng)前的最后一條邊然后新邊接到最后一條邊的nxt上。不過大多數(shù)競賽題不要求順序所以頭插法足夠了知道這點(diǎn)能避免很多無謂的煩惱。5.4 忘記處理重邊和自環(huán)鏈?zhǔn)角跋蛐潜旧聿粫詣尤ブ匾膊粫芙^自環(huán)。如果你的算法要求處理重邊比如最短路、最小生成樹要自己在邊權(quán)取min或者在讀取時(shí)判斷一下。自環(huán)u到u的邊在鏈?zhǔn)角跋蛐抢飼徽４鎯捅闅v這通常是正確的但在某些特殊DP或圖論性質(zhì)題中自環(huán)可能導(dǎo)致狀態(tài)轉(zhuǎn)移死循環(huán)需要在轉(zhuǎn)移時(shí)判斷v ! u或者用vis數(shù)組標(biāo)記。我踩過的一個(gè)真實(shí)坑是寫B(tài)ellman-Ford時(shí)因?yàn)樽原h(huán)邊不斷更新dist程序陷入了死循環(huán)。后來排查了很久才發(fā)現(xiàn)是自環(huán)造成的。所以如果你用鏈?zhǔn)角跋蛐桥苓@類基于邊數(shù)循環(huán)的算法務(wù)必考慮自環(huán)的影響。5.5 多組測試數(shù)據(jù)的清零問題多組測試時(shí)很多人只memset了head卻忘了其他數(shù)組其實(shí)不需要完全清零——只要不越界讀取頭插法添加邊時(shí)to、nxt、weight都會被覆蓋所以不清理沒問題。但head必須清否則上一組數(shù)據(jù)遺留的邊頭會讓新的遍歷跑到無效的舊邊。有一種更節(jié)省時(shí)間的操作用一個(gè)時(shí)間戳數(shù)組或者記錄每組數(shù)據(jù)的邊起點(diǎn)位置從上次的cnt開始繼續(xù)用不清空head也能避免越界。不過這種騷操作只適合對性能極致敏感的題目大多數(shù)時(shí)候老老實(shí)實(shí)memset就夠了。5.6 用鏈表頭插法寫錯(cuò)nxt指向?qū)慳dd時(shí)最容易寫錯(cuò)的是nxt[cnt] head[u]和head[u] cnt的順序。正確做法是“先托孤再奪位”先把新邊的next指向原來的頭再把頭指向新邊。如果寫反了會出現(xiàn)環(huán)或者丟邊。這一點(diǎn)在每個(gè)見到鏈?zhǔn)角跋蛐堑娜松砩蠋缀醵及l(fā)生過所以單獨(dú)提出來。另外用遞歸DFS時(shí)注意棧溢出問題。鏈?zhǔn)角跋蛐谴鎴D后遞歸深度可能達(dá)到n而某些評測環(huán)境?？臻g很小比如Windows下的某些編譯器只有1MB這時(shí)可以把遞歸改成顯式棧模擬。圖論的DFS遞歸寫法在n10^5級別一般還能承受但n更大或者需要多次DFS時(shí)就要小心了。6. 實(shí)操建議什么時(shí)候首選鏈?zhǔn)角跋蛐且约澳０宸窒?.1 決策思路總結(jié)根據(jù)我個(gè)人的實(shí)戰(zhàn)經(jīng)驗(yàn)在下面幾種情況我基本無腦選鏈?zhǔn)角跋蛐琼旤c(diǎn)數(shù)n在10^4以上邊數(shù)m在10^5以上需要高頻遍歷一個(gè)點(diǎn)的所有鄰邊且這種遍歷會執(zhí)行很多輪要寫網(wǎng)絡(luò)流等需要反向邊的算法對內(nèi)存有限制的題目數(shù)組比vector更可控在C/C競賽環(huán)境中為了穩(wěn)定性想避開vector擴(kuò)容的波動。如果只是做LeetCode上的簡單圖題n經(jīng)常只有幾百vector就夠了真沒必要上鏈?zhǔn)角跋蛐?。但如果你打算長期搞算法競賽練熟鏈?zhǔn)角跋蛐菐缀跏且坏辣剡^的門檻因?yàn)樗軒湍憷斫狻皵?shù)組模擬鏈表”這一大類的核心思想后面遇到鏈?zhǔn)焦１怼㈧o態(tài)Treap、并查集的可撤銷版本時(shí)思路都會自然得多。6.2 一個(gè)可以直接抄的通用模板我把常用寫法整理成一個(gè)模板平時(shí)做題直接在這個(gè)基礎(chǔ)上改就行#include bits/stdc.h using namespace std; const int N 100005; const int M 200005; int head[N], to[M], nxt[M], weight[M]; int cnt 0; inline void add(int u, int v, int w) { to[cnt] v; weight[cnt] w; nxt[cnt] head[u]; head[u] cnt; } void dfs(int u, int fa) { for (int i head[u]; i; i nxt[i]) { // 這里如果head用-1初始化條件就是 i ! -1 int v to[i]; if (v fa) continue; dfs(v, u); // 可以在這里做樹上DP或統(tǒng)計(jì) } } int main() { memset(head, -1, sizeof(head)); // 讀邊 int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; add(u, v, w); add(v, u, w); // 無向圖 } dfs(1, 0); return 0; }注意我注釋里提到的一個(gè)細(xì)節(jié)這段代碼里如果head初始化為-1遍歷條件必須是i ! -1如果在某個(gè)版本里我用0當(dāng)空標(biāo)記那head初始化成0遍歷條件就是i ! 0。這兩種寫法我都見過但一個(gè)程序里只能混用一種。建議用-1因?yàn)?號位置在cnt從1開始時(shí)本來就不使用不會引發(fā)歧義。6.3 和現(xiàn)代C語法結(jié)合的小改進(jìn)如果你用C17或C20可以給鏈?zhǔn)角跋蛐前b成一個(gè)結(jié)構(gòu)體簡化多組數(shù)據(jù)時(shí)的初始化struct Graph { int cnt 0; vectorint head, to, nxt, w; Graph(int n, int m) : head(n 1, -1), to(m 5), nxt(m 5), w(m 5) {} void add(int u, int v, int weight 0) { to[cnt] v; w[cnt] weight; nxt[cnt] head[u]; head[u] cnt; } };這樣每次構(gòu)造一個(gè)Graph對象就自動分配好內(nèi)存并初始化head為-1不用每次手動memset。實(shí)測下來代碼可讀性更好也不容易初始化漏掉。缺點(diǎn)是多一層對象封裝可能有一點(diǎn)點(diǎn)性能損耗但多數(shù)情況下影響微乎其微。如果在極限性能要求的題目里還是建議寫全局?jǐn)?shù)組畢竟競賽環(huán)境下全局?jǐn)?shù)組零初始化就是最穩(wěn)定的選擇。在實(shí)際寫題過程中我還發(fā)現(xiàn)鏈?zhǔn)角跋蛐菍φ{(diào)試很友好因?yàn)槟惆堰吋蟹旁跀?shù)組里打印某個(gè)點(diǎn)鄰邊時(shí)可以很方便地輸出邊的編號、to和next調(diào)試信息非常直觀。而vector鄰接表雖然也能打印但沒法同時(shí)看到“下一條邊”這個(gè)維度。所以從調(diào)試角度講鏈?zhǔn)角跋蛐瞧鋵?shí)并沒有想象中那么“反人類”反而幫你把鏈表結(jié)構(gòu)可視化出來。剛開始接觸鏈?zhǔn)角跋蛐菚r(shí)我建議你花半小時(shí)做一件事自己用紙筆模擬一個(gè)5個(gè)點(diǎn)6條邊的圖按add的步驟寫下每次更新后的head數(shù)組、to數(shù)組、nxt數(shù)組然后手動走一遍遍歷過程。這個(gè)練習(xí)能讓你徹底擺脫“背代碼”的狀態(tài)真正理解它為什么能串起一條邊鏈表。有了這種手感之后不管面試還是比賽里遇到什么樣包裝的圖存儲題你都能一眼看穿底層的結(jié)構(gòu)關(guān)系。另外如果你用C寫題可以留意一下開啟編譯優(yōu)化后的差距。鏈?zhǔn)角跋蛐桥浜?O2優(yōu)化編譯循環(huán)里的數(shù)組訪問通常會被優(yōu)化得很好vector版本在開啟優(yōu)化后差距會縮小一些但極端情況下鏈?zhǔn)角跋蛐侨匀桓€(wěn)。所以在本地評測和線上評測環(huán)境不一致時(shí)選鏈?zhǔn)角跋蛐悄軠p少一些“本地過了線上超時(shí)”的玄學(xué)問題。最后再分享一個(gè)我自己判斷是否使用鏈?zhǔn)角跋蛐堑慕?jīng)驗(yàn)先看數(shù)據(jù)范圍如果n和m接近或者m遠(yuǎn)大于n那就偏向用鄰接矩陣但這通常只在n比較小時(shí)成立如果m和n同量級或者m只是n的幾倍那就是典型的稀疏圖鏈?zhǔn)角跋蛐腔騰ector都行如果題目明確要求處理反向邊、殘量網(wǎng)絡(luò)這種結(jié)構(gòu)鏈?zhǔn)角跋蛐且麛鄡?yōu)先。數(shù)據(jù)結(jié)構(gòu)這東西沒有絕對的最好只有場景下的最適合能把鏈?zhǔn)角跋蛐呛蛌ector鄰接表都熟練在手才是真正的圖論基本功。 深入理解鏈?zhǔn)角跋蛐牵簲?shù)組模擬鄰接表的原理、實(shí)現(xiàn)與應(yīng)用
鏈?zhǔn)角跋蛐沁@個(gè)名詞在很多初學(xué)者眼里屬于那種“聽說過但一直沒搞懂”的存在尤其是刷LeetCode、備戰(zhàn)算法競賽、考研數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)的時(shí)候總是繞不開它。我第一次接觸這個(gè)結(jié)構(gòu)是在做圖論題被vector鄰接表反復(fù)超時(shí)之后才真正下決心把它啃下來。這一篇我盡量把鏈?zhǔn)角跋蛐堑脑?、?shí)現(xiàn)、應(yīng)用和坑一次講清楚讓它成為你順手就能用的工具而不是只停留在收藏夾里的名詞。這個(gè)內(nèi)容適合誰正在準(zhǔn)備算法競賽的選手、考研或保研面試需要扎實(shí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的同學(xué)以及工作中需要用C/Java等語言實(shí)現(xiàn)高性能圖算法的人。鏈?zhǔn)角跋蛐墙鉀Q的核心問題其實(shí)很簡單在稀疏圖中如何用內(nèi)存更緊湊、常數(shù)更小的方式存儲圖的鄰接關(guān)系同時(shí)保證遍歷鄰接邊的高效。它本質(zhì)上是一種用數(shù)組模擬鏈表實(shí)現(xiàn)鄰接表的方法但比vector套vector的實(shí)現(xiàn)更可控比鄰接矩陣內(nèi)存占用小得多在網(wǎng)絡(luò)流、最短路、樹形DP等場景里都有非常廣泛的應(yīng)用。1. 鏈?zhǔn)角跋蛐堑谋举|(zhì)用數(shù)組模擬“帶索引的鄰接鏈表”1.1 從圖的存儲需求說起先想想我們存儲一張有向圖或無向圖時(shí)到底需要什么對每個(gè)頂點(diǎn)u要知道它和哪些頂點(diǎn)相連以及每條邊的權(quán)重如果有的話。最簡單的鄰接矩陣用一個(gè)n乘n的二維數(shù)組存查詢兩個(gè)點(diǎn)是否有邊是O(1)但空間是O(n^2)。當(dāng)n達(dá)到10^5邊數(shù)只有2*10^5時(shí)鄰接矩陣就是災(zāi)難光初始化一個(gè)10^5乘10^5的二維數(shù)組就夠你內(nèi)存爆掉。于是大家自然轉(zhuǎn)向鄰接表對每個(gè)頂點(diǎn)u維護(hù)一個(gè)列表里面存從u出發(fā)的所有邊。這個(gè)列表在C里最容易想到的實(shí)現(xiàn)就是vector adj[N]需要存權(quán)重時(shí)再用vectorpairint,int或者定義結(jié)構(gòu)體。vector實(shí)現(xiàn)簡單、思維負(fù)擔(dān)小所以很多人入門圖論時(shí)都用它?？蓡栴}在于vector不是為高頻插入和遍歷而生的每次push_back可能觸發(fā)內(nèi)存重新分配涉及拷貝和搬移遍歷時(shí)雖然是連續(xù)的但多個(gè)vector分布在不同內(nèi)存塊里整體緩存命中率不一定好。鏈?zhǔn)角跋蛐亲龅氖虑榫褪前选懊總€(gè)頂點(diǎn)的鄰接邊列表”用一條邏輯上的鏈表串起來而且整條鏈表的所有結(jié)點(diǎn)都放在幾個(gè)全局?jǐn)?shù)組里。它不依賴動態(tài)分配不依賴vector的實(shí)現(xiàn)細(xì)節(jié)而是自己管理“下一個(gè)結(jié)點(diǎn)是誰”。理解它之后你會發(fā)現(xiàn)它其實(shí)就是手寫了一個(gè)非常輕量的鄰接表。1.2 鏈?zhǔn)角跋蛐堑娜齻€(gè)核心數(shù)組鏈?zhǔn)角跋蛐峭ǔ＞S護(hù)三個(gè)數(shù)組或再加一個(gè)權(quán)重?cái)?shù)組head[u]表示從頂點(diǎn)u出發(fā)的第一條邊在邊數(shù)組中的下標(biāo)也可以理解為鏈表頭指針。to[i]第i條邊指向的終點(diǎn)頂點(diǎn)。nxt[i]第i條邊的下一條邊在下標(biāo)數(shù)組中的位置即鏈表的后繼指針。w[i]第i條邊的權(quán)值若需要。這里數(shù)組的下標(biāo)i是邊的編號每條邊的編號在添加時(shí)被確定。添加一條邊時(shí)采用頭插法新的邊結(jié)點(diǎn)插入到頂點(diǎn)u的鏈表頭部。也就是說void addEdge(int u, int v, int w) { to[cnt] v; // 邊的終點(diǎn) weight[cnt] w; // 邊的權(quán)值 nxt[cnt] head[u]; // 新邊的下一條邊指向原來u的第一條邊 head[u] cnt; // 更新u的鏈表頭為新邊 }看到這個(gè)操作是不是覺得特別像單鏈表的頭插法對它就是單鏈表。區(qū)別在于普通單鏈表的結(jié)點(diǎn)是動態(tài)new出來的要用指針連接鏈?zhǔn)角跋蛐怯脭?shù)組下標(biāo)指向下一個(gè)結(jié)點(diǎn)所以它的“指針”是一個(gè)int。這也是為什么它常被稱為“靜態(tài)鄰接表”。用一個(gè)生活化的類比來理解假設(shè)每個(gè)頂點(diǎn)是一個(gè)抽屜head[u]是抽屜里放的那張索引卡片卡片上寫著“第一條邊的編號”。每條邊的信息終點(diǎn)、權(quán)值、下一條邊的編號登記在賬本的某一行。頭插法相當(dāng)于每次來了新信息先在賬本上記一行然后更新抽屜里的卡片讓卡片指向最新一行同時(shí)在新一行里寫上“上一行是哪一行”。這樣從任一條邊出發(fā)都能沿著“下一條邊”的指引把整個(gè)抽屜里的邊全部翻出來。1.3 為什么它能提升性能連續(xù)性與可控性鏈?zhǔn)角跋蛐堑暮诵膬?yōu)勢之一是所有邊都存放在連續(xù)的數(shù)組里。用vector存鄰接表時(shí)雖然單個(gè)頂點(diǎn)的邊是連續(xù)存儲的但不同頂點(diǎn)的邊分散在不同vector中而鏈?zhǔn)角扒靶前阉羞吔y(tǒng)一放在幾個(gè)數(shù)組里更像是一塊連續(xù)的內(nèi)存被不同鏈表分塊占用。對CPU緩存來說連續(xù)數(shù)組的遍歷比其他零散分配的對象友好很多尤其當(dāng)你的算法需要反復(fù)遍歷某個(gè)頂點(diǎn)的所有鄰邊時(shí)這種友好會被放大。另一層優(yōu)勢是“可控”。vector的擴(kuò)容時(shí)機(jī)由標(biāo)準(zhǔn)庫決定在競賽這種對時(shí)間極其敏感的場景里你不知道某次push_back會觸發(fā)多大代價(jià)的重新分配。鏈?zhǔn)角跋蛐莿t不同只要你提前算好最大邊數(shù)開一個(gè)定長數(shù)組就完全避免動態(tài)分配所有內(nèi)存一次到位。再加上它的“指針”只是int下標(biāo)比64位指針小一半同樣存10萬條邊存儲開銷更低。這些優(yōu)勢疊加起來在圖規(guī)模比較大、算法常數(shù)要求高的題里可能就是壓線通過和超時(shí)的區(qū)別。2. 核心實(shí)現(xiàn)與每一步的原理拆解2.1 一張圖看懂添加和遍歷先看一個(gè)具體例子我們手動模擬一下向圖中添加幾條邊的過程這樣可以建立非常直觀的印象。假設(shè)有一張有向圖頂點(diǎn)1到22到31到3的邊按這個(gè)順序添加。初始時(shí)head[1]-1head[2]-1head[3]-1cnt0這里我用-1表示空鏈表。添加邊1-2cnt變成1to[1]2nxt[1]head[1]-1head[1]1。這時(shí)的鏈表狀態(tài)head[1]指向邊1邊1的next為-1。添加邊2-3cnt變成2to[2]3nxt[2]head[2]-1head[2]2。添加邊1-3cnt變成3to[3]3nxt[3]head[1]1head[1]3?，F(xiàn)在如果遍歷頂點(diǎn)1的所有出邊i head[1] 3訪問to[3]3這條路i nxt[3] 1訪問to[1]2這條路i nxt[1] -1遍歷結(jié)束?？吹?jīng)]有遍歷順序是倒過來的先添加的邊1-2反而后被訪問到。這是頭插法的天然特性大多數(shù)情況下順序不影響正確性但如果你依賴邊的訪問順序要記得這一點(diǎn)。這也是很多新手寫代碼時(shí)一時(shí)反應(yīng)不過來的地方。遍歷代碼很簡單for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; // 當(dāng)前邊指向的頂點(diǎn) int w weight[i]; // 當(dāng)前邊的權(quán)重 // 在這里處理業(yè)務(wù)邏輯 }這段代碼非?！皺C(jī)械”可以說是鏈?zhǔn)角跋蛐堑墓潭▽懛ū诚聛砭托?。關(guān)鍵是要理解為什么i nxt[i]能走到下一條邊以及為什么循環(huán)停止條件是i -1。2.2 頭插法與數(shù)組下標(biāo)管理細(xì)則添加邊的函數(shù)里有一個(gè)極其關(guān)鍵的細(xì)節(jié)cnt到底從0開始還是從1開始以及用cnt還是cnt這直接影響后面很多問題的處理。我習(xí)慣用以下的寫法const int N 100005; const int M 2 * 200005; // 無向圖注意開兩倍邊數(shù) int head[N], to[M], nxt[M], weight[M]; int cnt 0; inline void add(int u, int v, int w) { to[cnt] v; weight[cnt] w; nxt[cnt] head[u]; head[u] cnt; }這里cnt從0開始每次先再使用所以邊的編號從1開始。這樣有一個(gè)隱藏好處如果某道題里你在某個(gè)數(shù)組位置存了一個(gè)哨兵值0號位置不會被實(shí)際邊占用便于記憶和檢查。當(dāng)然也可以讓cnt從0開始使用0號位置這樣編號從0開始不過程序員之間的習(xí)慣差異很大重要的是你選一種并堅(jiān)持一致。初始化時(shí)head數(shù)組全部置為-1memset(head, -1, sizeof(head));有人會問為什么不用0表示空鏈表用0也行但需要把cnt初始化為0且add時(shí)用cnt而不是cnt并且還要額外設(shè)置0號位置的值。如果你用-1表示空代碼里所有遍歷的結(jié)束條件都寫成i ! -1語義非常明確。我建議新手一開始就用-1減少邊界條件混亂。2.3 有向圖、無向圖和反向邊問題鏈?zhǔn)角跋蛐翘幚碛邢驁D就是直接add(u, v, w)就完事。無向圖則要添加兩次add(u, v, w)和add(v, u, w)分別表示兩條方向相反的邊。這里有一個(gè)很多競賽選手愛用的經(jīng)典技巧如果添加無向邊時(shí)先add(u,v,w)再add(v,u,w)那么這兩條邊的編號分別為cnt1和cnt2并且滿足關(guān)系1號邊和2號邊互為反向邊3號邊和4號邊互為反向邊……更一般地說編號i和i^1是互為反向邊。這個(gè)性質(zhì)在處理網(wǎng)絡(luò)流算法時(shí)需要快速找反向邊極其有用。void addUndirected(int u, int v, int w) { add(u, v, w); add(v, u, w); } // 若需要訪問某條邊i的反向邊直接訪問 i ^ 1 即可這個(gè)“異或1”的技巧是鏈?zhǔn)角跋蛐窃诰W(wǎng)絡(luò)流題里的殺手锏之一。用vector鄰接表時(shí)你得在結(jié)構(gòu)體里存rev字段或者費(fèi)勁維護(hù)反向邊的位置而鏈?zhǔn)角跋蛐翘烊痪邆溥@個(gè)性質(zhì)。所以如果你準(zhǔn)備學(xué)Dinic、SAP這類算法鏈?zhǔn)角跋蛐菐缀跏潜貙W(xué)的前置內(nèi)容。3. 鏈?zhǔn)角跋蛐桥c主流存圖方式的橫向?qū)Ρ?.1 三種存圖方式的核心參數(shù)對比為了更直觀地看出區(qū)別我平時(shí)做題時(shí)會用這個(gè)表來做決策存儲方式空間復(fù)雜度判斷兩點(diǎn)是否相鄰遍歷某頂點(diǎn)所有鄰邊適用場景鄰接矩陣O(n^2)O(1)O(n)n很小通常1000以內(nèi)需要考慮稠密圖、需要頻繁判斷兩點(diǎn)是否相鄰vector鄰接表O(nm)需要遍歷列表最壞O(deg)O(deg)常數(shù)較大常規(guī)圖論題、實(shí)現(xiàn)簡單對性能不極致要求鏈?zhǔn)角跋蛐荗(nm)常數(shù)小需要遍歷列表同左O(deg)常數(shù)小數(shù)組連續(xù)大規(guī)模稀疏圖、網(wǎng)絡(luò)流、對時(shí)間和內(nèi)存限制嚴(yán)格的競賽題從工程上的直觀體感來說n10^5、m2*10^5級別的時(shí)候鏈?zhǔn)角跋蛐潜闅v鄰接邊的總時(shí)間大概是vector鄰接表的60%-80%。這個(gè)數(shù)字取決于編譯器和系統(tǒng)環(huán)境但趨勢是一致的。如果你的題目里需要跑很多輪遍歷比如反復(fù)做多源BFS、Dijkstra堆優(yōu)化里的多次松弛差距會被拉得更大。3.2 為什么說鏈?zhǔn)角跋蛐歉m合競賽和高性能場景很多人覺得既然有了vector為什么還要背鏈?zhǔn)角跋蛐菃栴}在于vector本質(zhì)是動態(tài)數(shù)組每次push_back遇到容量不夠時(shí)會重新分配內(nèi)存把舊內(nèi)容搬到新內(nèi)存里。這個(gè)過程雖然是均攤O(1)但單次操作可能突然變慢而且分配器本身也有開銷。在競賽評測機(jī)那種極端場景下有的題目就卡在這種常數(shù)上。而鏈?zhǔn)角跋蛐鞘恰笆止れo態(tài)分配”。你知道最多有多少條邊就把數(shù)組開夠。添加邊只是幾次數(shù)組賦值連內(nèi)存分配都沒有。同時(shí)因?yàn)樗羞叾荚谕粋€(gè)數(shù)組里遍歷的緩存局部性更好尤其當(dāng)你只需要訪問邊的終點(diǎn)、權(quán)值、下一條邊這三個(gè)字段時(shí)CPU可以把整塊數(shù)組搬到高速緩存里效率遠(yuǎn)高于分散在堆上的vector結(jié)點(diǎn)。這有點(diǎn)類似數(shù)據(jù)庫里“聚集索引”和“分散索引”的區(qū)別數(shù)據(jù)如果能物理連續(xù)地放在一起范圍掃描就會快很多。鏈?zhǔn)角跋蛐前堰叺慕Y(jié)構(gòu)天然聚集在同一片連續(xù)內(nèi)存里所以它跑掃描式的圖算法遍歷每個(gè)點(diǎn)的鄰邊確實(shí)有物理層面的優(yōu)勢。3.3 什么情況下不要執(zhí)念鏈?zhǔn)角跋蛐擎準(zhǔn)角跋蛐遣⒎侨f能。如果你的圖規(guī)模不大比如n在1000以內(nèi)或者你用的是Python、Java這類語言鏈?zhǔn)角跋蛐堑膬?yōu)勢會被語言本身的數(shù)組對象開銷稀釋。Python里你寫list套list反而更直觀而且Python的列表對象和循環(huán)開銷本身就是瓶頸手寫數(shù)組模擬并不能從根本上改變復(fù)雜度。再比如需要頻繁刪邊的場景鏈?zhǔn)角跋蛐亲觥拔锢韯h除”很麻煩。雖然你可以加一個(gè)vis標(biāo)記打懶標(biāo)記但如果你真的需要不斷地刪除某條邊、恢復(fù)某條邊動態(tài)鏈表或者平衡樹結(jié)構(gòu)會更合適。鏈?zhǔn)角跋蛐沁m合“建圖之后反復(fù)讀邊幾乎不做結(jié)構(gòu)修改”的場景這恰好覆蓋了絕大多數(shù)圖論算法題。4. 鏈?zhǔn)角跋蛐窃诮?jīng)典算法中的應(yīng)用4.1 堆優(yōu)化Dijkstra中的鏈?zhǔn)角跋蛐亲疃搪匪惴ɡ镦準(zhǔn)角跋蛐鞘嵌褍?yōu)化Dijkstra的固定搭檔。原因在于Dijkstra的核心操作是從優(yōu)先隊(duì)列里取出距離最小的點(diǎn)然后遍歷這個(gè)點(diǎn)的所有出邊嘗試松弛。這個(gè)過程對鄰接表的“遍歷”需求極其頻繁每一條出邊都要被訪問一次。用鏈?zhǔn)角跋蛐菍懗鰜矸浅Ｗ匀籿oid dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; int w weight[i]; if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }這段代碼里遍歷部分就是鏈?zhǔn)角跋蛐堑臉?biāo)準(zhǔn)循環(huán)沒有顯式的“遍歷索引”也沒有復(fù)雜的迭代器就三個(gè)數(shù)組三個(gè)變量清爽干凈。先把dist初始化成無窮大用0x3f可以避免加法溢出每次取出當(dāng)前最小點(diǎn)如果堆里的距離不是最新的就跳過這就是“惰性刪除”策略。4.2 DFS、BFS與樹DP的配套寫法DFS和BFS同樣可以直接套鏈?zhǔn)角跋蛐?。DFS的遞歸寫法void dfs(int u, int fa) { for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; if (v fa) continue; // 處理從u到v的邊 dfs(v, u); } }樹形DP時(shí)這個(gè)dfs里經(jīng)常要結(jié)合子樹信息做狀態(tài)轉(zhuǎn)移。比如求樹的重心、樹的直徑、子樹大小之類的問題鏈?zhǔn)角跋蛐潜闅v子節(jié)點(diǎn)非常合適。因?yàn)槊總€(gè)節(jié)點(diǎn)出邊的順序并不重要而鏈?zhǔn)酱鎯κ沟脧母腹?jié)點(diǎn)到子節(jié)點(diǎn)的跳躍只依賴一次數(shù)組下標(biāo)訪問。BFS的寫法也很直接用一個(gè)隊(duì)列存頂點(diǎn)每次彈出一個(gè)u就遍歷head[u]開頭的鏈表將所有未訪問的v入隊(duì)。整個(gè)過程中不需要像鄰接矩陣那樣對無關(guān)頂點(diǎn)也掃描一遍所以復(fù)雜度是O(nm)。4.3 網(wǎng)絡(luò)流算法中的反向邊利器網(wǎng)絡(luò)流算法Edmonds-Karp、Dinic、ISAP都需要維護(hù)殘量網(wǎng)絡(luò)核心操作之一就是不斷找到一條增廣路后對路徑上的邊的容量做減法并對反向邊容量做加法。這時(shí)前面提到的i^1技巧派上了用場你只要把邊從1開始編號保證每加入一條正向邊后立刻加入它的反向邊那么正向邊和反向邊的編號就是相鄰的異或1就能互相找到。我自己寫Dinic時(shí)一條addEdge函數(shù)inline void addEdge(int u, int v, int c) { to[cnt] v; cap[cnt] c; nxt[cnt] head[u]; head[u] cnt; to[cnt] u; cap[cnt] 0; nxt[cnt] head[v]; head[v] cnt; }正向邊容量c反向邊容量0。更新時(shí)int cur i ^ 1; cap[i] - flow; cap[cur] flow;這樣寫比vector版本清爽很多因?yàn)関ector需要你手動記錄反向邊在哪個(gè)位置甚至需要在結(jié)構(gòu)體里維護(hù)一個(gè)int rev。鏈?zhǔn)角跋蛐翘焐逊聪蜻吔壎ㄔ诰幪柈惢蜿P(guān)系上不用額外存儲自然成為圖論競賽選手網(wǎng)絡(luò)流題的首選。5. 常見問題與排查手把手解決鏈?zhǔn)角跋蛐堑目?.1 數(shù)組越界無向圖邊的數(shù)量要乘2這是我見過最多新手踩的坑。題目說m條無向邊你開數(shù)組時(shí)如果只開m大小那add兩次的時(shí)候第m1次添加就會越界。正確做法是至少開2m為了保險(xiǎn)我通常開2m5。有人可能會問為什么不是m5因?yàn)闊o向邊會拆成兩條有向邊存儲所以添加次數(shù)是2m。如果你開了m5的大小可能在本地測試小數(shù)據(jù)時(shí)一切正常一到大數(shù)據(jù)就直接RE運(yùn)行時(shí)錯(cuò)誤或者本地跑得慢提交上去返回段錯(cuò)誤。排查方法很簡單先檢查你的全局?jǐn)?shù)組大小是不是除以2了。5.2 head數(shù)組初始化為-1 vs 0和判重沖突鏈?zhǔn)角跋蛐堑呐袛鄺l件是i ! -1所以head初始化為-1非常關(guān)鍵。如果忘了初始化head里的值可能是0或者垃圾值導(dǎo)致遍歷時(shí)從錯(cuò)誤的邊開始甚至訪問到未定義的數(shù)組位置。多組測試數(shù)據(jù)時(shí)記得在每組數(shù)據(jù)開始前把head重新memset為-1。另外如果你使用0號邊作為哨兵那么head初始化為0并且add時(shí)用cnt先用0號位置再自增那么遍歷條件是i ! 0。這種寫法也可以但新手容易在調(diào)試時(shí)把0和-1搞混。我自己的建議是統(tǒng)一用-1別混用。5.3 遍歷順序相反導(dǎo)致結(jié)果不對鏈?zhǔn)角跋蛐鞘穷^插法所以邊的遍歷順序和添加順序相反。如果你在算法里依賴“先訪問到某條邊”的順序就很容易出bug。比如有些DP題需要按輸入的邊順序處理有些題需要你按特定順序輸出路徑這時(shí)別慌可以通過調(diào)整添加順序或者翻轉(zhuǎn)邏輯來修正。有個(gè)小技巧如果你希望遍歷順序和輸入順序一致可以在add的時(shí)候插入到鏈尾而不是鏈頭也就是維護(hù)一個(gè)tail數(shù)組記錄每個(gè)點(diǎn)當(dāng)前的最后一條邊然后新邊接到最后一條邊的nxt上。不過大多數(shù)競賽題不要求順序所以頭插法足夠了知道這點(diǎn)能避免很多無謂的煩惱。5.4 忘記處理重邊和自環(huán)鏈?zhǔn)角跋蛐潜旧聿粫詣尤ブ匾膊粫芙^自環(huán)。如果你的算法要求處理重邊比如最短路、最小生成樹要自己在邊權(quán)取min或者在讀取時(shí)判斷一下。自環(huán)u到u的邊在鏈?zhǔn)角跋蛐抢飼徽４鎯捅闅v這通常是正確的但在某些特殊DP或圖論性質(zhì)題中自環(huán)可能導(dǎo)致狀態(tài)轉(zhuǎn)移死循環(huán)需要在轉(zhuǎn)移時(shí)判斷v ! u或者用vis數(shù)組標(biāo)記。我踩過的一個(gè)真實(shí)坑是寫B(tài)ellman-Ford時(shí)因?yàn)樽原h(huán)邊不斷更新dist程序陷入了死循環(huán)。后來排查了很久才發(fā)現(xiàn)是自環(huán)造成的。所以如果你用鏈?zhǔn)角跋蛐桥苓@類基于邊數(shù)循環(huán)的算法務(wù)必考慮自環(huán)的影響。5.5 多組測試數(shù)據(jù)的清零問題多組測試時(shí)很多人只memset了head卻忘了其他數(shù)組其實(shí)不需要完全清零——只要不越界讀取頭插法添加邊時(shí)to、nxt、weight都會被覆蓋所以不清理沒問題。但head必須清否則上一組數(shù)據(jù)遺留的邊頭會讓新的遍歷跑到無效的舊邊。有一種更節(jié)省時(shí)間的操作用一個(gè)時(shí)間戳數(shù)組或者記錄每組數(shù)據(jù)的邊起點(diǎn)位置從上次的cnt開始繼續(xù)用不清空head也能避免越界。不過這種騷操作只適合對性能極致敏感的題目大多數(shù)時(shí)候老老實(shí)實(shí)memset就夠了。5.6 用鏈表頭插法寫錯(cuò)nxt指向?qū)慳dd時(shí)最容易寫錯(cuò)的是nxt[cnt] head[u]和head[u] cnt的順序。正確做法是“先托孤再奪位”先把新邊的next指向原來的頭再把頭指向新邊。如果寫反了會出現(xiàn)環(huán)或者丟邊。這一點(diǎn)在每個(gè)見到鏈?zhǔn)角跋蛐堑娜松砩蠋缀醵及l(fā)生過所以單獨(dú)提出來。另外用遞歸DFS時(shí)注意棧溢出問題。鏈?zhǔn)角跋蛐谴鎴D后遞歸深度可能達(dá)到n而某些評測環(huán)境?？臻g很小比如Windows下的某些編譯器只有1MB這時(shí)可以把遞歸改成顯式棧模擬。圖論的DFS遞歸寫法在n10^5級別一般還能承受但n更大或者需要多次DFS時(shí)就要小心了。6. 實(shí)操建議什么時(shí)候首選鏈?zhǔn)角跋蛐且约澳０宸窒?.1 決策思路總結(jié)根據(jù)我個(gè)人的實(shí)戰(zhàn)經(jīng)驗(yàn)在下面幾種情況我基本無腦選鏈?zhǔn)角跋蛐琼旤c(diǎn)數(shù)n在10^4以上邊數(shù)m在10^5以上需要高頻遍歷一個(gè)點(diǎn)的所有鄰邊且這種遍歷會執(zhí)行很多輪要寫網(wǎng)絡(luò)流等需要反向邊的算法對內(nèi)存有限制的題目數(shù)組比vector更可控在C/C競賽環(huán)境中為了穩(wěn)定性想避開vector擴(kuò)容的波動。如果只是做LeetCode上的簡單圖題n經(jīng)常只有幾百vector就夠了真沒必要上鏈?zhǔn)角跋蛐?。但如果你打算長期搞算法競賽練熟鏈?zhǔn)角跋蛐菐缀跏且坏辣剡^的門檻因?yàn)樗軒湍憷斫狻皵?shù)組模擬鏈表”這一大類的核心思想后面遇到鏈?zhǔn)焦１怼㈧o態(tài)Treap、并查集的可撤銷版本時(shí)思路都會自然得多。6.2 一個(gè)可以直接抄的通用模板我把常用寫法整理成一個(gè)模板平時(shí)做題直接在這個(gè)基礎(chǔ)上改就行#include bits/stdc.h using namespace std; const int N 100005; const int M 200005; int head[N], to[M], nxt[M], weight[M]; int cnt 0; inline void add(int u, int v, int w) { to[cnt] v; weight[cnt] w; nxt[cnt] head[u]; head[u] cnt; } void dfs(int u, int fa) { for (int i head[u]; i; i nxt[i]) { // 這里如果head用-1初始化條件就是 i ! -1 int v to[i]; if (v fa) continue; dfs(v, u); // 可以在這里做樹上DP或統(tǒng)計(jì) } } int main() { memset(head, -1, sizeof(head)); // 讀邊 int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; add(u, v, w); add(v, u, w); // 無向圖 } dfs(1, 0); return 0; }注意我注釋里提到的一個(gè)細(xì)節(jié)這段代碼里如果head初始化為-1遍歷條件必須是i ! -1如果在某個(gè)版本里我用0當(dāng)空標(biāo)記那head初始化成0遍歷條件就是i ! 0。這兩種寫法我都見過但一個(gè)程序里只能混用一種。建議用-1因?yàn)?號位置在cnt從1開始時(shí)本來就不使用不會引發(fā)歧義。6.3 和現(xiàn)代C語法結(jié)合的小改進(jìn)如果你用C17或C20可以給鏈?zhǔn)角跋蛐前b成一個(gè)結(jié)構(gòu)體簡化多組數(shù)據(jù)時(shí)的初始化struct Graph { int cnt 0; vectorint head, to, nxt, w; Graph(int n, int m) : head(n 1, -1), to(m 5), nxt(m 5), w(m 5) {} void add(int u, int v, int weight 0) { to[cnt] v; w[cnt] weight; nxt[cnt] head[u]; head[u] cnt; } };這樣每次構(gòu)造一個(gè)Graph對象就自動分配好內(nèi)存并初始化head為-1不用每次手動memset。實(shí)測下來代碼可讀性更好也不容易初始化漏掉。缺點(diǎn)是多一層對象封裝可能有一點(diǎn)點(diǎn)性能損耗但多數(shù)情況下影響微乎其微。如果在極限性能要求的題目里還是建議寫全局?jǐn)?shù)組畢竟競賽環(huán)境下全局?jǐn)?shù)組零初始化就是最穩(wěn)定的選擇。在實(shí)際寫題過程中我還發(fā)現(xiàn)鏈?zhǔn)角跋蛐菍φ{(diào)試很友好因?yàn)槟惆堰吋蟹旁跀?shù)組里打印某個(gè)點(diǎn)鄰邊時(shí)可以很方便地輸出邊的編號、to和next調(diào)試信息非常直觀。而vector鄰接表雖然也能打印但沒法同時(shí)看到“下一條邊”這個(gè)維度。所以從調(diào)試角度講鏈?zhǔn)角跋蛐瞧鋵?shí)并沒有想象中那么“反人類”反而幫你把鏈表結(jié)構(gòu)可視化出來。剛開始接觸鏈?zhǔn)角跋蛐菚r(shí)我建議你花半小時(shí)做一件事自己用紙筆模擬一個(gè)5個(gè)點(diǎn)6條邊的圖按add的步驟寫下每次更新后的head數(shù)組、to數(shù)組、nxt數(shù)組然后手動走一遍遍歷過程。這個(gè)練習(xí)能讓你徹底擺脫“背代碼”的狀態(tài)真正理解它為什么能串起一條邊鏈表。有了這種手感之后不管面試還是比賽里遇到什么樣包裝的圖存儲題你都能一眼看穿底層的結(jié)構(gòu)關(guān)系。另外如果你用C寫題可以留意一下開啟編譯優(yōu)化后的差距。鏈?zhǔn)角跋蛐桥浜?O2優(yōu)化編譯循環(huán)里的數(shù)組訪問通常會被優(yōu)化得很好vector版本在開啟優(yōu)化后差距會縮小一些但極端情況下鏈?zhǔn)角跋蛐侨匀桓€(wěn)。所以在本地評測和線上評測環(huán)境不一致時(shí)選鏈?zhǔn)角跋蛐悄軠p少一些“本地過了線上超時(shí)”的玄學(xué)問題。最后再分享一個(gè)我自己判斷是否使用鏈?zhǔn)角跋蛐堑慕?jīng)驗(yàn)先看數(shù)據(jù)范圍如果n和m接近或者m遠(yuǎn)大于n那就偏向用鄰接矩陣但這通常只在n比較小時(shí)成立如果m和n同量級或者m只是n的幾倍那就是典型的稀疏圖鏈?zhǔn)角跋蛐腔騰ector都行如果題目明確要求處理反向邊、殘量網(wǎng)絡(luò)這種結(jié)構(gòu)鏈?zhǔn)角跋蛐且麛鄡?yōu)先。數(shù)據(jù)結(jié)構(gòu)這東西沒有絕對的最好只有場景下的最適合能把鏈?zhǔn)角跋蛐呛蛌ector鄰接表都熟練在手才是真正的圖論基本功。