據(jù)結(jié)構(gòu)詳解)
1. 從鄰接表到十字鏈表一個“有向”問題的誕生在數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和工程實踐中圖的存儲結(jié)構(gòu)一直是個核心話題。我們最熟悉的莫過于鄰接矩陣和鄰接表。鄰接矩陣直觀但空間復(fù)雜度是O(n2)對于稀疏圖簡直是災(zāi)難。鄰接表則靈活得多它用一個數(shù)組存儲所有頂點每個頂點后面掛著一個鏈表鏈表的節(jié)點代表了從這個頂點出發(fā)的邊。對于無向圖鄰接表很完美一條邊會在兩個頂點的鏈表中各出現(xiàn)一次空間復(fù)雜度O(VE)查找一個頂點的出邊也很快。但當(dāng)我們把目光投向有向圖時鄰接表的“小瑕疵”就暴露出來了。假設(shè)我們有一個描述微博關(guān)注關(guān)系的有向圖頂點是用戶一條從A指向B的邊表示A關(guān)注了B。用鄰接表存儲我們很容易回答“A關(guān)注了哪些人”查A的出邊鏈表。但如果產(chǎn)品經(jīng)理問你“哪些人關(guān)注了B”即查找B的入邊鄰接表就尷尬了。你需要遍歷所有頂點的鏈表才能找出那些指向B的邊時間復(fù)雜度是O(VE)。這在頂點數(shù)巨大比如百萬級用戶時是無法接受的性能瓶頸。這就是十字鏈表法要解決的“有向”痛點。它不是一個憑空創(chuàng)造的全新結(jié)構(gòu)而是對鄰接表的一次精妙“升級”目標(biāo)很明確在保留鄰接表查找出邊高效的前提下同樣高效地支持查找入邊。你可以把它理解為給鄰接表的每個邊節(jié)點加了“反向指針”讓邊與邊之間形成了縱橫交錯的“十字”鏈接因此得名。理解十字鏈表不僅能幫你應(yīng)對數(shù)據(jù)結(jié)構(gòu)考試中關(guān)于圖存儲的各類變體題更能讓你在設(shè)計涉及密集關(guān)系查詢?nèi)缟缃痪W(wǎng)絡(luò)、任務(wù)依賴分析、知識圖譜的系統(tǒng)時多一個底層數(shù)據(jù)組織的利器。2. 十字鏈表的“骨架”頂點與邊的精確定義要理解十字鏈表我們必須先拆解它的兩個基本構(gòu)件頂點節(jié)點和邊節(jié)點。這與鄰接表有相似之處但鏈接關(guān)系更為復(fù)雜和對稱。2.1 頂點節(jié)點信息中樞與鏈表頭頂點節(jié)點是整個結(jié)構(gòu)的入口和樞紐。它至少需要包含兩部分信息數(shù)據(jù)域存儲頂點的實際信息比如用戶的ID、城市的名稱、任務(wù)的編號等。指針域這里就是十字鏈表與鄰接表分道揚(yáng)鑣的關(guān)鍵。一個頂點節(jié)點需要維護(hù)兩個鏈表的頭指針。firstIn指向以該頂點為終點弧頭的第一條邊即第一條入邊所在的邊節(jié)點。通過這個指針我們可以快速找到所有“指向我”的邊。firstOut指向以該頂點為起點弧尾的第一條邊即第一條出邊所在的邊節(jié)點。這個指針的功能和鄰接表的頭指針一致用于快速找到所有“我指向”的邊。所有頂點節(jié)點通常存儲在一個順序數(shù)組頂點表中這樣我們可以通過頂點下標(biāo)O(1)地訪問任何一個頂點并拿到它的firstIn和firstOut指針。2.2 邊節(jié)點十字交錯的核心載體邊節(jié)點是十字鏈表最精妙的部分它像一張網(wǎng)中的連接點同時屬于兩個鏈表。一個邊節(jié)點通常包含以下五個域以有向邊tailVex, headVex為例即從頂點tailVex指向頂點headVextailVex 邊的起點弧尾頂點在頂點表中的下標(biāo)。headVex 邊的終點弧頭頂點在頂點表中的下標(biāo)。weight 邊的權(quán)值如果是帶權(quán)圖。hLink橫向鏈接指針。它指向與當(dāng)前邊擁有相同弧頭headVex相同的下一條邊。所有弧頭相同的邊通過hLink串成一個鏈表這個鏈表的頭就是頂點表中headVex那個頂點的firstIn。因此hLink串起來的是入邊鏈表。tLink縱向鏈接指針。它指向與當(dāng)前邊擁有相同弧尾tailVex相同的下一條邊。所有弧尾相同的邊通過tLink串成一個鏈表這個鏈表的頭就是頂點表中tailVex那個頂點的firstOut。因此tLink串起來的是出邊鏈表。這里有一個非常關(guān)鍵的理解一個邊節(jié)點同時存在于兩個鏈表中。它既在起點的出邊鏈表里通過tLink連接也在終點的入邊鏈表里通過hLink連接。這就像一個人既在“我關(guān)注的人”列表里也在“關(guān)注我的人”列表里但物理上只存在一個“人”的實體。為了更直觀我們構(gòu)造一個簡單的有向圖包含4個頂點V0, V1, V2, V3和有向邊V0, V1,V0, V2,V1, V2,V2, V0,V2, V3。其十字鏈表存儲結(jié)構(gòu)如下圖所示為簡化省略權(quán)值頂點表: 下標(biāo) | 數(shù)據(jù) | firstIn | firstOut --------------------------------- 0 | V0 | [2] | [0] 1 | V1 | [0] | [2] 2 | V2 | [1],[3]| [4] 3 | V3 | [4] | null 邊節(jié)點池 ([]內(nèi)為邊節(jié)點編號): [0]: tail0, head1, hLinknull, tLink[1] [1]: tail0, head2, hLink[3], tLinknull [2]: tail1, head2, hLink[3], tLinknull [3]: tail2, head0, hLinknull, tLink[4] [4]: tail2, head3, hLinknull, tLinknull 鏈表關(guān)系解讀 - V0的出邊鏈表(firstOut-[0]): [0] --tLink-- [1] - null。即V0指向V1和V2。 - V0的入邊鏈表(firstIn-[3]): [3] - null。即只有V2指向V0。 - V2的入邊鏈表(firstIn-[1]): [1] --hLink-- [2] - null。即V0和V1都指向V2。 - V2的出邊鏈表(firstOut-[4]): [4] --tLink-- [3] - null? 等等這里需要檢查。 實際上[4]的tLink是null[3]的tLink是[4]。所以V2的出邊鏈表是firstOut-[4]? 不對。 根據(jù)定義firstOut應(yīng)指向以V2為tail的第一條邊。我們看邊節(jié)點tail2的有[3]和[4]。 我們需要約定插入順序。假設(shè)按邊列表順序插入 插入2,0為[3]此時V2.firstOut[3]。 插入2,3為[4]將[4]的tLink指向V2當(dāng)前firstOut即[3]然后更新V2.firstOut[4]。 因此V2的出邊鏈表是firstOut-[4] --tLink-- [3] - null。即V2指向V3和V0。從這個例子可以看到查詢V2的所有入邊只需從V2.firstIn([1])開始沿hLink遍歷即可獲得[1]和[2]對應(yīng)邊0,2和1,2非常高效。3. 十字鏈表的構(gòu)建、遍歷與核心操作剖析理解了靜態(tài)結(jié)構(gòu)我們來看看如何動態(tài)地構(gòu)建和維護(hù)一個十字鏈表以及如何利用它進(jìn)行高效的查詢。3.1 圖的建立插入邊的藝術(shù)假設(shè)我們已經(jīng)有了頂點數(shù)組構(gòu)建十字鏈表的過程就是依次插入每條有向邊的過程。插入一條新邊u, v權(quán)值為w的算法步驟如下它清晰地展示了兩個鏈表是如何被同時維護(hù)的創(chuàng)建邊節(jié)點在邊節(jié)點池可以是一個動態(tài)數(shù)組或內(nèi)存池中申請一個新節(jié)點e。設(shè)置e.tailVex u,e.headVex v,e.weight w。鏈接到出邊鏈表縱向tLink將e.tLink指向頂點u當(dāng)前firstOut指針?biāo)赶虻倪吂?jié)點即e.tLink vertex[u].firstOut。然后更新頂點u的firstOut指針指向新節(jié)點e即vertex[u].firstOut e。為什么是頭插法頭插法實現(xiàn)簡單時間復(fù)雜度為O(1)。如果采用尾插法則需要遍歷找到鏈表尾部需要O(出度)的時間。對于建圖這個通常一次性或批量完成的操作頭插法是更常見的選擇。鏈接到入邊鏈表橫向hLink將e.hLink指向頂點v當(dāng)前firstIn指針?biāo)赶虻倪吂?jié)點即e.hLink vertex[v].firstIn。然后更新頂點v的firstIn指針指向新節(jié)點e即vertex[v].firstIn e。這個過程就像把一根新線邊節(jié)點同時穿入兩個不同的線團(tuán)出邊鏈表和入邊鏈表。頭插法的結(jié)果是每個鏈表中的邊節(jié)點順序與插入順序相反。但這通常不影響查詢功能。實操心得在實現(xiàn)時特別是用C/C這類語言要特別注意對空指針的處理。在第二步和第三步中如果vertex[u].firstOut或vertex[v].firstIn原本就是NULL那么e.tLink或e.hLink自然就被設(shè)置為NULL這正好表示它是鏈表的最后一個節(jié)點。代碼邏輯是統(tǒng)一的不需要特殊分支判斷。3.2 核心查詢操作展現(xiàn)雙向高效性十字鏈表的優(yōu)勢在查詢時體現(xiàn)得淋漓盡致。查找頂點u的所有出邊EdgeNode *p vertex[u].firstOut; while (p ! NULL) { // 處理邊 u - p-headVex權(quán)值為 p-weight printf(- %d (weight: %d)\n, p-headVex, p-weight); p p-tLink; // 沿著縱向鏈表走 }這和鄰接表的遍歷完全一樣時間復(fù)雜度為O(出度(u))。查找頂點v的所有入邊EdgeNode *p vertex[v].firstIn; while (p ! NULL) { // 處理邊 p-tailVex - v權(quán)值為 p-weight printf(- %d (weight: %d)\n, p-tailVex, p-weight); p p-hLink; // 沿著橫向鏈表走 }這是十字鏈表獨有的高效操作時間復(fù)雜度為O(入度(v))。而在鄰接表中這需要O(VE)。判斷是否存在邊u, v 這需要遍歷u的出邊鏈表或v的入邊鏈表。最壞情況是O(max(出度(u), 入度(v)))。雖然比鄰接矩陣的O(1)差但對于稀疏圖這通常是可以接受的。如果判斷操作極其頻繁且圖較密可能需要結(jié)合其他數(shù)據(jù)結(jié)構(gòu)如哈希表來優(yōu)化。3.3 圖的遍歷深度優(yōu)先與廣度優(yōu)先基于十字鏈表的圖遍歷DFS/BFS算法與基于鄰接表的版本在邏輯上幾乎完全一致只需要將“訪問鄰接點”的操作從遍歷鄰接表換成遍歷某個頂點的出邊鏈表即可。因為遍歷通常是從一個頂點“向外”探索。例如DFS的遞歸核心部分void DFS(OLGraph G, int v) { visited[v] true; // 遍歷v的所有出邊即v能到達(dá)的頂點 for (EdgeNode *p G.vertex[v].firstOut; p ! NULL; p p-tLink) { int w p-headVex; // w是v的鄰接點 if (!visited[w]) { DFS(G, w); } } }BFS同理將隊列中頂點的出邊鏈表中的未訪問節(jié)點入隊。注意事項如果你實現(xiàn)的算法需要同時考慮入邊和出邊例如某些強(qiáng)連通分量算法那么十字鏈表firstIn的便利性就體現(xiàn)出來了你可以輕松獲取一個頂點的“前驅(qū)”集合而無需遍歷整個圖。4. 十字鏈表的性能權(quán)衡與工程實踐思考沒有一種數(shù)據(jù)結(jié)構(gòu)是完美的十字鏈表是在特定需求下對空間和時間做出的精妙權(quán)衡。4.1 復(fù)雜度分析空間換時間空間復(fù)雜度存儲V個頂點節(jié)點和E個邊節(jié)點。頂點節(jié)點包含數(shù)據(jù)和兩個指針。邊節(jié)點包含兩個頂點下標(biāo)、權(quán)值可選和兩個指針。粗略估算為O(V E)。與鄰接表相比邊節(jié)點多了一個指針hLink因此空間開銷比鄰接表大約多出O(E)。這是為了獲得高效入邊查詢而付出的代價。時間復(fù)雜度建圖插入一條邊是O(1)建圖整體為O(E)。查出入邊查詢頂點v的所有出邊為O(出度(v))查詢所有入邊為O(入度(v))。這是其核心優(yōu)勢。增刪邊插入邊如前所述是O(1)。刪除一條指定的邊則相對麻煩因為需要在其所在的出邊鏈表和入邊鏈表中都找到它的前驅(qū)節(jié)點來更新鏈接最壞需要O(出度(u)入度(v))。如果刪除操作頻繁需要維護(hù)雙向鏈表或額外指針來優(yōu)化。4.2 對比與選型何時該用十字鏈表讓我們將其與鄰接矩陣、鄰接表放在一起對比特性鄰接矩陣鄰接表十字鏈表空間O(V2)O(VE)O(VE)略高于鄰接表查邊u,vO(1)O(出度(u))或O(入度(v))需遍歷O(出度(u))或O(入度(v))找出邊O(V)需掃描一行O(出度(u))O(出度(u))找入邊O(V)需掃描一列O(VE)需遍歷所有邊O(入度(v))增邊O(1)O(1)頭插O(1)刪邊O(1)O(出度(u))或O(入度(v)出度(u))O(出度(u)入度(v))適用場景稠密圖頻繁查邊通用尤其稀疏圖側(cè)重出邊操作有向圖且需頻繁、高效查詢?nèi)脒呥x型建議默認(rèn)選擇鄰接表對于大多數(shù)無向圖或者雖然有向但入邊查詢需求不強(qiáng)烈的場景鄰接表簡單、空間效率高是首選。十字鏈表的主場當(dāng)你的應(yīng)用嚴(yán)重依賴“查找指向某個頂點的所有邊”這一操作時十字鏈表的優(yōu)勢無可替代。典型場景包括社交網(wǎng)絡(luò)分析分析用戶的粉絲入邊列表。任務(wù)調(diào)度與依賴分析查找哪些任務(wù)是當(dāng)前任務(wù)的前置條件入邊。編譯器技術(shù)在程序依賴圖、控制流圖中分析某個基本塊被哪些塊跳轉(zhuǎn)而來。知識圖譜查詢某個實體被哪些關(guān)系或?qū)嶓w所指向。鄰接矩陣僅適用于頂點數(shù)很少或極度稠密邊數(shù)接近V2且需要頻繁進(jìn)行O(1)復(fù)雜度的邊存在性判斷的場景。4.3 實現(xiàn)細(xì)節(jié)與避坑指南在實際編碼實現(xiàn)十字鏈表時有幾個細(xì)節(jié)容易出錯邊節(jié)點的唯一性一條有向邊在十字鏈表中只對應(yīng)一個物理邊節(jié)點。這個節(jié)點通過tLink和hLink被兩個鏈表共享。任何對邊節(jié)點內(nèi)容的修改如權(quán)值更新都會在兩個鏈表中同時生效這符合邏輯但編程時要心中有數(shù)。刪除操作的陷阱刪除邊u, v對應(yīng)的節(jié)點e時必須分別在u的出邊鏈表和v的入邊鏈表中找到e的前驅(qū)節(jié)點才能正確更新鏈表鏈接。如果鏈表是單向的這個過程需要遍歷。一種優(yōu)化方案是將邊節(jié)點設(shè)計為雙向鏈表節(jié)點增加tLinkPrev和hLinkPrev指針這樣刪除時就能在O(1)時間內(nèi)找到前驅(qū)但空間開銷會進(jìn)一步增加。這再次體現(xiàn)了工程中的權(quán)衡。內(nèi)存管理如果邊節(jié)點是動態(tài)申請的new/malloc在析構(gòu)圖結(jié)構(gòu)時需要妥善釋放所有邊節(jié)點。由于邊節(jié)點被兩個鏈表共享切忌重復(fù)釋放。標(biāo)準(zhǔn)的做法是遍歷頂點數(shù)組對于每個頂點遍歷其firstOut鏈表或firstIn鏈表依次釋放邊節(jié)點并注意在釋放后將該節(jié)點的指針置空避免懸空指針。由于一個邊節(jié)點一定會出現(xiàn)在某個頂點的firstOut鏈表中所以遍歷所有頂點的出邊鏈表足以覆蓋所有邊節(jié)點。序列化與持久化將十字鏈表存儲到文件或數(shù)據(jù)庫會比較復(fù)雜因為包含了大量的指針內(nèi)存地址。通常需要將圖數(shù)據(jù)轉(zhuǎn)化為邊列表(u, v, w)這樣的三元組序列進(jìn)行存儲加載時再重新構(gòu)建十字鏈表結(jié)構(gòu)。我個人在實現(xiàn)一個代碼依賴分析工具時就選擇了十字鏈表來存儲函數(shù)調(diào)用圖。我需要頻繁地分析“這個函數(shù)被哪些函數(shù)調(diào)用”入邊查詢十字鏈表讓這個核心查詢操作變得極其高效雖然增加了約1/3的內(nèi)存開銷但帶來的性能提升在百萬級函數(shù)調(diào)用關(guān)系的分析中是決定性的。這正印證了那句話在軟件工程中沒有最好的數(shù)據(jù)結(jié)構(gòu)只有最適合當(dāng)前場景的數(shù)據(jù)結(jié)構(gòu)。十字鏈表就是為“有向圖且重視入邊”這一特定場景而生的精致解決方案。 十字鏈表：高效處理有向圖入邊查詢的數(shù)據(jù)結(jié)構(gòu)詳解
1. 從鄰接表到十字鏈表一個“有向”問題的誕生在數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和工程實踐中圖的存儲結(jié)構(gòu)一直是個核心話題。我們最熟悉的莫過于鄰接矩陣和鄰接表。鄰接矩陣直觀但空間復(fù)雜度是O(n2)對于稀疏圖簡直是災(zāi)難。鄰接表則靈活得多它用一個數(shù)組存儲所有頂點每個頂點后面掛著一個鏈表鏈表的節(jié)點代表了從這個頂點出發(fā)的邊。對于無向圖鄰接表很完美一條邊會在兩個頂點的鏈表中各出現(xiàn)一次空間復(fù)雜度O(VE)查找一個頂點的出邊也很快。但當(dāng)我們把目光投向有向圖時鄰接表的“小瑕疵”就暴露出來了。假設(shè)我們有一個描述微博關(guān)注關(guān)系的有向圖頂點是用戶一條從A指向B的邊表示A關(guān)注了B。用鄰接表存儲我們很容易回答“A關(guān)注了哪些人”查A的出邊鏈表。但如果產(chǎn)品經(jīng)理問你“哪些人關(guān)注了B”即查找B的入邊鄰接表就尷尬了。你需要遍歷所有頂點的鏈表才能找出那些指向B的邊時間復(fù)雜度是O(VE)。這在頂點數(shù)巨大比如百萬級用戶時是無法接受的性能瓶頸。這就是十字鏈表法要解決的“有向”痛點。它不是一個憑空創(chuàng)造的全新結(jié)構(gòu)而是對鄰接表的一次精妙“升級”目標(biāo)很明確在保留鄰接表查找出邊高效的前提下同樣高效地支持查找入邊。你可以把它理解為給鄰接表的每個邊節(jié)點加了“反向指針”讓邊與邊之間形成了縱橫交錯的“十字”鏈接因此得名。理解十字鏈表不僅能幫你應(yīng)對數(shù)據(jù)結(jié)構(gòu)考試中關(guān)于圖存儲的各類變體題更能讓你在設(shè)計涉及密集關(guān)系查詢?nèi)缟缃痪W(wǎng)絡(luò)、任務(wù)依賴分析、知識圖譜的系統(tǒng)時多一個底層數(shù)據(jù)組織的利器。2. 十字鏈表的“骨架”頂點與邊的精確定義要理解十字鏈表我們必須先拆解它的兩個基本構(gòu)件頂點節(jié)點和邊節(jié)點。這與鄰接表有相似之處但鏈接關(guān)系更為復(fù)雜和對稱。2.1 頂點節(jié)點信息中樞與鏈表頭頂點節(jié)點是整個結(jié)構(gòu)的入口和樞紐。它至少需要包含兩部分信息數(shù)據(jù)域存儲頂點的實際信息比如用戶的ID、城市的名稱、任務(wù)的編號等。指針域這里就是十字鏈表與鄰接表分道揚(yáng)鑣的關(guān)鍵。一個頂點節(jié)點需要維護(hù)兩個鏈表的頭指針。firstIn指向以該頂點為終點弧頭的第一條邊即第一條入邊所在的邊節(jié)點。通過這個指針我們可以快速找到所有“指向我”的邊。firstOut指向以該頂點為起點弧尾的第一條邊即第一條出邊所在的邊節(jié)點。這個指針的功能和鄰接表的頭指針一致用于快速找到所有“我指向”的邊。所有頂點節(jié)點通常存儲在一個順序數(shù)組頂點表中這樣我們可以通過頂點下標(biāo)O(1)地訪問任何一個頂點并拿到它的firstIn和firstOut指針。2.2 邊節(jié)點十字交錯的核心載體邊節(jié)點是十字鏈表最精妙的部分它像一張網(wǎng)中的連接點同時屬于兩個鏈表。一個邊節(jié)點通常包含以下五個域以有向邊tailVex, headVex為例即從頂點tailVex指向頂點headVextailVex 邊的起點弧尾頂點在頂點表中的下標(biāo)。headVex 邊的終點弧頭頂點在頂點表中的下標(biāo)。weight 邊的權(quán)值如果是帶權(quán)圖。hLink橫向鏈接指針。它指向與當(dāng)前邊擁有相同弧頭headVex相同的下一條邊。所有弧頭相同的邊通過hLink串成一個鏈表這個鏈表的頭就是頂點表中headVex那個頂點的firstIn。因此hLink串起來的是入邊鏈表。tLink縱向鏈接指針。它指向與當(dāng)前邊擁有相同弧尾tailVex相同的下一條邊。所有弧尾相同的邊通過tLink串成一個鏈表這個鏈表的頭就是頂點表中tailVex那個頂點的firstOut。因此tLink串起來的是出邊鏈表。這里有一個非常關(guān)鍵的理解一個邊節(jié)點同時存在于兩個鏈表中。它既在起點的出邊鏈表里通過tLink連接也在終點的入邊鏈表里通過hLink連接。這就像一個人既在“我關(guān)注的人”列表里也在“關(guān)注我的人”列表里但物理上只存在一個“人”的實體。為了更直觀我們構(gòu)造一個簡單的有向圖包含4個頂點V0, V1, V2, V3和有向邊V0, V1,V0, V2,V1, V2,V2, V0,V2, V3。其十字鏈表存儲結(jié)構(gòu)如下圖所示為簡化省略權(quán)值頂點表: 下標(biāo) | 數(shù)據(jù) | firstIn | firstOut --------------------------------- 0 | V0 | [2] | [0] 1 | V1 | [0] | [2] 2 | V2 | [1],[3]| [4] 3 | V3 | [4] | null 邊節(jié)點池 ([]內(nèi)為邊節(jié)點編號): [0]: tail0, head1, hLinknull, tLink[1] [1]: tail0, head2, hLink[3], tLinknull [2]: tail1, head2, hLink[3], tLinknull [3]: tail2, head0, hLinknull, tLink[4] [4]: tail2, head3, hLinknull, tLinknull 鏈表關(guān)系解讀 - V0的出邊鏈表(firstOut-[0]): [0] --tLink-- [1] - null。即V0指向V1和V2。 - V0的入邊鏈表(firstIn-[3]): [3] - null。即只有V2指向V0。 - V2的入邊鏈表(firstIn-[1]): [1] --hLink-- [2] - null。即V0和V1都指向V2。 - V2的出邊鏈表(firstOut-[4]): [4] --tLink-- [3] - null? 等等這里需要檢查。 實際上[4]的tLink是null[3]的tLink是[4]。所以V2的出邊鏈表是firstOut-[4]? 不對。 根據(jù)定義firstOut應(yīng)指向以V2為tail的第一條邊。我們看邊節(jié)點tail2的有[3]和[4]。 我們需要約定插入順序。假設(shè)按邊列表順序插入 插入2,0為[3]此時V2.firstOut[3]。 插入2,3為[4]將[4]的tLink指向V2當(dāng)前firstOut即[3]然后更新V2.firstOut[4]。 因此V2的出邊鏈表是firstOut-[4] --tLink-- [3] - null。即V2指向V3和V0。從這個例子可以看到查詢V2的所有入邊只需從V2.firstIn([1])開始沿hLink遍歷即可獲得[1]和[2]對應(yīng)邊0,2和1,2非常高效。3. 十字鏈表的構(gòu)建、遍歷與核心操作剖析理解了靜態(tài)結(jié)構(gòu)我們來看看如何動態(tài)地構(gòu)建和維護(hù)一個十字鏈表以及如何利用它進(jìn)行高效的查詢。3.1 圖的建立插入邊的藝術(shù)假設(shè)我們已經(jīng)有了頂點數(shù)組構(gòu)建十字鏈表的過程就是依次插入每條有向邊的過程。插入一條新邊u, v權(quán)值為w的算法步驟如下它清晰地展示了兩個鏈表是如何被同時維護(hù)的創(chuàng)建邊節(jié)點在邊節(jié)點池可以是一個動態(tài)數(shù)組或內(nèi)存池中申請一個新節(jié)點e。設(shè)置e.tailVex u,e.headVex v,e.weight w。鏈接到出邊鏈表縱向tLink將e.tLink指向頂點u當(dāng)前firstOut指針?biāo)赶虻倪吂?jié)點即e.tLink vertex[u].firstOut。然后更新頂點u的firstOut指針指向新節(jié)點e即vertex[u].firstOut e。為什么是頭插法頭插法實現(xiàn)簡單時間復(fù)雜度為O(1)。如果采用尾插法則需要遍歷找到鏈表尾部需要O(出度)的時間。對于建圖這個通常一次性或批量完成的操作頭插法是更常見的選擇。鏈接到入邊鏈表橫向hLink將e.hLink指向頂點v當(dāng)前firstIn指針?biāo)赶虻倪吂?jié)點即e.hLink vertex[v].firstIn。然后更新頂點v的firstIn指針指向新節(jié)點e即vertex[v].firstIn e。這個過程就像把一根新線邊節(jié)點同時穿入兩個不同的線團(tuán)出邊鏈表和入邊鏈表。頭插法的結(jié)果是每個鏈表中的邊節(jié)點順序與插入順序相反。但這通常不影響查詢功能。實操心得在實現(xiàn)時特別是用C/C這類語言要特別注意對空指針的處理。在第二步和第三步中如果vertex[u].firstOut或vertex[v].firstIn原本就是NULL那么e.tLink或e.hLink自然就被設(shè)置為NULL這正好表示它是鏈表的最后一個節(jié)點。代碼邏輯是統(tǒng)一的不需要特殊分支判斷。3.2 核心查詢操作展現(xiàn)雙向高效性十字鏈表的優(yōu)勢在查詢時體現(xiàn)得淋漓盡致。查找頂點u的所有出邊EdgeNode *p vertex[u].firstOut; while (p ! NULL) { // 處理邊 u - p-headVex權(quán)值為 p-weight printf(- %d (weight: %d)\n, p-headVex, p-weight); p p-tLink; // 沿著縱向鏈表走 }這和鄰接表的遍歷完全一樣時間復(fù)雜度為O(出度(u))。查找頂點v的所有入邊EdgeNode *p vertex[v].firstIn; while (p ! NULL) { // 處理邊 p-tailVex - v權(quán)值為 p-weight printf(- %d (weight: %d)\n, p-tailVex, p-weight); p p-hLink; // 沿著橫向鏈表走 }這是十字鏈表獨有的高效操作時間復(fù)雜度為O(入度(v))。而在鄰接表中這需要O(VE)。判斷是否存在邊u, v 這需要遍歷u的出邊鏈表或v的入邊鏈表。最壞情況是O(max(出度(u), 入度(v)))。雖然比鄰接矩陣的O(1)差但對于稀疏圖這通常是可以接受的。如果判斷操作極其頻繁且圖較密可能需要結(jié)合其他數(shù)據(jù)結(jié)構(gòu)如哈希表來優(yōu)化。3.3 圖的遍歷深度優(yōu)先與廣度優(yōu)先基于十字鏈表的圖遍歷DFS/BFS算法與基于鄰接表的版本在邏輯上幾乎完全一致只需要將“訪問鄰接點”的操作從遍歷鄰接表換成遍歷某個頂點的出邊鏈表即可。因為遍歷通常是從一個頂點“向外”探索。例如DFS的遞歸核心部分void DFS(OLGraph G, int v) { visited[v] true; // 遍歷v的所有出邊即v能到達(dá)的頂點 for (EdgeNode *p G.vertex[v].firstOut; p ! NULL; p p-tLink) { int w p-headVex; // w是v的鄰接點 if (!visited[w]) { DFS(G, w); } } }BFS同理將隊列中頂點的出邊鏈表中的未訪問節(jié)點入隊。注意事項如果你實現(xiàn)的算法需要同時考慮入邊和出邊例如某些強(qiáng)連通分量算法那么十字鏈表firstIn的便利性就體現(xiàn)出來了你可以輕松獲取一個頂點的“前驅(qū)”集合而無需遍歷整個圖。4. 十字鏈表的性能權(quán)衡與工程實踐思考沒有一種數(shù)據(jù)結(jié)構(gòu)是完美的十字鏈表是在特定需求下對空間和時間做出的精妙權(quán)衡。4.1 復(fù)雜度分析空間換時間空間復(fù)雜度存儲V個頂點節(jié)點和E個邊節(jié)點。頂點節(jié)點包含數(shù)據(jù)和兩個指針。邊節(jié)點包含兩個頂點下標(biāo)、權(quán)值可選和兩個指針。粗略估算為O(V E)。與鄰接表相比邊節(jié)點多了一個指針hLink因此空間開銷比鄰接表大約多出O(E)。這是為了獲得高效入邊查詢而付出的代價。時間復(fù)雜度建圖插入一條邊是O(1)建圖整體為O(E)。查出入邊查詢頂點v的所有出邊為O(出度(v))查詢所有入邊為O(入度(v))。這是其核心優(yōu)勢。增刪邊插入邊如前所述是O(1)。刪除一條指定的邊則相對麻煩因為需要在其所在的出邊鏈表和入邊鏈表中都找到它的前驅(qū)節(jié)點來更新鏈接最壞需要O(出度(u)入度(v))。如果刪除操作頻繁需要維護(hù)雙向鏈表或額外指針來優(yōu)化。4.2 對比與選型何時該用十字鏈表讓我們將其與鄰接矩陣、鄰接表放在一起對比特性鄰接矩陣鄰接表十字鏈表空間O(V2)O(VE)O(VE)略高于鄰接表查邊u,vO(1)O(出度(u))或O(入度(v))需遍歷O(出度(u))或O(入度(v))找出邊O(V)需掃描一行O(出度(u))O(出度(u))找入邊O(V)需掃描一列O(VE)需遍歷所有邊O(入度(v))增邊O(1)O(1)頭插O(1)刪邊O(1)O(出度(u))或O(入度(v)出度(u))O(出度(u)入度(v))適用場景稠密圖頻繁查邊通用尤其稀疏圖側(cè)重出邊操作有向圖且需頻繁、高效查詢?nèi)脒呥x型建議默認(rèn)選擇鄰接表對于大多數(shù)無向圖或者雖然有向但入邊查詢需求不強(qiáng)烈的場景鄰接表簡單、空間效率高是首選。十字鏈表的主場當(dāng)你的應(yīng)用嚴(yán)重依賴“查找指向某個頂點的所有邊”這一操作時十字鏈表的優(yōu)勢無可替代。典型場景包括社交網(wǎng)絡(luò)分析分析用戶的粉絲入邊列表。任務(wù)調(diào)度與依賴分析查找哪些任務(wù)是當(dāng)前任務(wù)的前置條件入邊。編譯器技術(shù)在程序依賴圖、控制流圖中分析某個基本塊被哪些塊跳轉(zhuǎn)而來。知識圖譜查詢某個實體被哪些關(guān)系或?qū)嶓w所指向。鄰接矩陣僅適用于頂點數(shù)很少或極度稠密邊數(shù)接近V2且需要頻繁進(jìn)行O(1)復(fù)雜度的邊存在性判斷的場景。4.3 實現(xiàn)細(xì)節(jié)與避坑指南在實際編碼實現(xiàn)十字鏈表時有幾個細(xì)節(jié)容易出錯邊節(jié)點的唯一性一條有向邊在十字鏈表中只對應(yīng)一個物理邊節(jié)點。這個節(jié)點通過tLink和hLink被兩個鏈表共享。任何對邊節(jié)點內(nèi)容的修改如權(quán)值更新都會在兩個鏈表中同時生效這符合邏輯但編程時要心中有數(shù)。刪除操作的陷阱刪除邊u, v對應(yīng)的節(jié)點e時必須分別在u的出邊鏈表和v的入邊鏈表中找到e的前驅(qū)節(jié)點才能正確更新鏈表鏈接。如果鏈表是單向的這個過程需要遍歷。一種優(yōu)化方案是將邊節(jié)點設(shè)計為雙向鏈表節(jié)點增加tLinkPrev和hLinkPrev指針這樣刪除時就能在O(1)時間內(nèi)找到前驅(qū)但空間開銷會進(jìn)一步增加。這再次體現(xiàn)了工程中的權(quán)衡。內(nèi)存管理如果邊節(jié)點是動態(tài)申請的new/malloc在析構(gòu)圖結(jié)構(gòu)時需要妥善釋放所有邊節(jié)點。由于邊節(jié)點被兩個鏈表共享切忌重復(fù)釋放。標(biāo)準(zhǔn)的做法是遍歷頂點數(shù)組對于每個頂點遍歷其firstOut鏈表或firstIn鏈表依次釋放邊節(jié)點并注意在釋放后將該節(jié)點的指針置空避免懸空指針。由于一個邊節(jié)點一定會出現(xiàn)在某個頂點的firstOut鏈表中所以遍歷所有頂點的出邊鏈表足以覆蓋所有邊節(jié)點。序列化與持久化將十字鏈表存儲到文件或數(shù)據(jù)庫會比較復(fù)雜因為包含了大量的指針內(nèi)存地址。通常需要將圖數(shù)據(jù)轉(zhuǎn)化為邊列表(u, v, w)這樣的三元組序列進(jìn)行存儲加載時再重新構(gòu)建十字鏈表結(jié)構(gòu)。我個人在實現(xiàn)一個代碼依賴分析工具時就選擇了十字鏈表來存儲函數(shù)調(diào)用圖。我需要頻繁地分析“這個函數(shù)被哪些函數(shù)調(diào)用”入邊查詢十字鏈表讓這個核心查詢操作變得極其高效雖然增加了約1/3的內(nèi)存開銷但帶來的性能提升在百萬級函數(shù)調(diào)用關(guān)系的分析中是決定性的。這正印證了那句話在軟件工程中沒有最好的數(shù)據(jù)結(jié)構(gòu)只有最適合當(dāng)前場景的數(shù)據(jù)結(jié)構(gòu)。十字鏈表就是為“有向圖且重視入邊”這一特定場景而生的精致解決方案。