構(gòu)精講)
1. 鄰接表在無向圖里為什么“存邊”存得別扭1.1 鄰接表的基本思路只有兩句話學(xué)圖存儲結(jié)構(gòu)時大多數(shù)人最先接觸的是鄰接矩陣和鄰接表。鄰接矩陣的思路很好理解開一個 n×n 的二維數(shù)組arc[i][j]為 1 就表示 i 到 j 之間有一條邊為 0 就沒有。判斷兩個頂點是否鄰接查一次數(shù)組下標(biāo)就完成了O(1) 的代價非常痛快。但它的短板也擺在明面上空間是 O(n2) 的頂點一多比如 5000 個頂點的稀疏圖光矩陣就要吃掉 25,000,000 個存儲單元大部分還是 0純屬浪費。鄰接表于是做了改進用“每個頂點掛一條鏈表”的方式把每個頂點的鄰接頂點串起來。每個頂點只需要一個頭節(jié)點再加若干條邊節(jié)點總空間降到了 O(ne)。這個思路簡潔、直覺所以幾乎所有教材都會把它當(dāng)作圖存儲的重點來講。但鄰接表解決的是“從一個頂點出發(fā)能找到哪些鄰居”的問題。一旦問題的對象從頂點換成邊鄰接表就開始露怯了。尤其是無向圖一條邊會被保存兩次從頂點 A 的角度看它有一條邊連向 B從頂點 B 的角度看它有一條邊連向 A。這聽起來不過是多存了一次但如果要做“刪除一條邊”“給一條邊打訪問標(biāo)記”“遍歷所有邊但每條邊只處理一次”這類操作麻煩就來了。1.2 “刪邊”在鄰接表里的連鎖反應(yīng)咱們用一個簡單例子推演一下。無向圖里有邊 (A, B)在鄰接表中必然存在兩個邊節(jié)點一個掛在 A 的鏈表里數(shù)據(jù)是 B一個掛在 B 的鏈表里數(shù)據(jù)是 A?，F(xiàn)在想讓這條邊消失程序至少要干四件事在 A 的鏈表中找到 B 的節(jié)點修改前驅(qū)節(jié)點的 next 指針釋放這個節(jié)點在 B 的鏈表中找到 A 的節(jié)點再次修改前驅(qū)節(jié)點的 next 指針再釋放一個節(jié)點。要注意的是這兩個節(jié)點雖然描述的是同一條邏輯邊但物理上完全是兩個獨立的內(nèi)存對象。如果只是在 A 那邊刪了B 那邊還掛著一個指向 A 的節(jié)點圖的狀態(tài)就錯了。更難受的是遍歷所有邊這種極其常見的需求在無向圖鄰接表里天然會把每條邊數(shù)兩遍你得額外加一個 visited 標(biāo)記或者設(shè)計去重邏輯寫起來特別容易漏。我把這種別扭總結(jié)成一句話鄰接表把“邊”這個對象拆成了兩份然后讓所有基于邊的操作都得先做一次‘去重’或‘同步’。鄰接多重表的出現(xiàn)就是專門為了避免這份別扭而設(shè)計的它在結(jié)構(gòu)上保證一條邊在物理上只出現(xiàn)一次邏輯上卻能同時掛在兩個頂點下面。這種存儲方式在無向圖里尤其是對邊頻繁操作的算法里比鄰接表又要舒服一個量級。2. 鄰接多重表的節(jié)點設(shè)計一條邊一個對象2.1 節(jié)點里的五個字段是干什么的先把結(jié)構(gòu)體的 C 語言定義擺出來這是理解鄰接多重表的骨架#define MAX_VERTEX_NUM 20 typedef struct EBox { int mark; // 標(biāo)記該邊是否被訪問過常用于遍歷 int ivex, jvex; // 該邊依附的兩個頂點在頂點表中的下標(biāo) struct EBox *ilink; // 指向下一條依附于頂點 ivex 的邊 struct EBox *jlink; // 指向下一條依附于頂點 jvex 的邊 int info; // 邊的權(quán)值普通圖可以不使用 } EBox; typedef struct VexBox { char data; // 頂點自身的值 EBox *firstedge; // 指向第一條依附于該頂點的邊 } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; } AMLGraph;看到這個結(jié)構(gòu)很多人的第一反應(yīng)是這不就是鄰接表嗎確實頂點表部分很像但邊節(jié)點部分是質(zhì)的區(qū)別。在鄰接表里邊節(jié)點里只有一個指針next指向下一個鄰接頂點在鄰接多重表里邊節(jié)點里有兩個指針ilink和jlink分別服務(wù)于邊的兩個端點。ivex和jvex存的是邊的兩個端點下標(biāo)沒有方向誰前誰后無所謂只要一條邊的兩端信息完整即可。ilink的含義是“指向下一條依附于 ivex 這個頂點的邊”jlink的含義是“指向下一條依附于 jvex 這個頂點的邊”。這兩個指針不是冗余備份而是各管一攤分別讓這條邊能夠同時掛進兩個頂點的鏈表中。mark字段像是給這條邊準(zhǔn)備的便簽紙。由于無向圖的邊天然沒有方向遍歷或搜索時如果不做標(biāo)記非常容易把同一條邊當(dāng)成兩條邊來訪問。有了mark你可以用它記錄“這條邊我已經(jīng)處理過了”算法跑一遍下來邊的訪問狀態(tài)清清楚楚。info字段則用來存權(quán)值比如邊的長度或代價需要用網(wǎng)圖時就有地方放了。2.2 五個字段如何撐起兩個并行的邊鏈表比較微妙的地方在于鄰接多重表里每個頂點依然有一條屬于自己的邊鏈表但鏈表里的節(jié)點是共享的。舉個例子無向圖有一條邊連接頂點 0 和頂點 3。創(chuàng)建這條邊時分配一個邊節(jié)點令ivex 0jvex 3。然后把這個節(jié)點同時插入到頂點 0 的邊鏈表中也插入到頂點 3 的邊鏈表中。也就是說這個物理節(jié)點同時出現(xiàn)在兩條鏈表中但它只占一份內(nèi)存。頂點 0 在遍歷自己的鄰接邊時怎么從當(dāng)前邊走到下一條邊呢必須判斷當(dāng)前節(jié)點里哪個下標(biāo)是 0。如果ivex 0就沿著ilink往下走否則說明 0 存在jvex里就沿著jlink往下走。同理從頂點 3 出發(fā)遍歷時也用同樣的判斷規(guī)則從ivex或者jvex中識別自己然后選擇對應(yīng)的鏈接。這種設(shè)計的本質(zhì)是把“這條邊在兩個頂點各自鏈表里的 next 指針”合并進了同一個邊節(jié)點。在鄰接表里一個邊對象存在于兩個獨立節(jié)點中同步維護它們之間的聯(lián)系只靠前驅(qū)節(jié)點。在鄰接多重表中一條邊只有一個節(jié)點但它帶著兩個指針分別通向它在兩個頂點鏈表里的下一條邊。因此你在任何一個頂點的鏈表里看到的都是一個完整的邊節(jié)點而不是一個殘缺的“鄰居編號”。實際寫代碼時最容易踩的坑就是這個判斷流程。很多初學(xué)者以為ilink永遠(yuǎn)是“左端點方向的下一跳”jlink永遠(yuǎn)是“右端點方向的下一跳”結(jié)果圖一建出來遍歷各種亂跳。要記住ilink只管ivex這個端點jlink只管jvex這個端點你可以把每個邊節(jié)點想象成一個十字路口兩個方向各有一條路需要去哪個端點就往哪個方向拐。3. 手寫鄰接多重表初始化、加邊、遍歷、刪邊3.1 初始化和插入邊的完整實現(xiàn)了解了結(jié)構(gòu)定義下一步就直接寫代碼。下面是一個可以直接跑起來的最小實現(xiàn)包含四個核心函數(shù)初始化圖、插入邊、打印每個頂點的鄰接信息、刪除邊。#include stdio.h #include stdlib.h #define MAX_VERTEX_NUM 20 typedef struct EBox { int mark; int ivex, jvex; struct EBox *ilink; struct EBox *jlink; int info; } EBox; typedef struct VexBox { char data; EBox *firstedge; } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; } AMLGraph; void InitGraph(AMLGraph *G, int vexnum) { G-vexnum vexnum; G-edgenum 0; for (int i 0; i vexnum; i) { G-adjmulist[i].firstedge NULL; } } void InsertEdge(AMLGraph *G, int i, int j) { EBox *p (EBox *)malloc(sizeof(EBox)); p-mark 0; p-ivex i; p-jvex j; p-info 0; // 將新邊插入頂點 i 的邊鏈表頭部 p-ilink G-adjmulist[i].firstedge; G-adjmulist[i].firstedge p; // 將同一條邊插入頂點 j 的邊鏈表頭部 p-jlink G-adjmulist[j].firstedge; G-adjmulist[j].firstedge p; G-edgenum; }插入邊用的是頭插法也就是每次都把新邊放到鏈表的第一個位置。頭插的好處是實現(xiàn)簡單不用維護尾指針。由于每個頂點都有自己的鏈表新邊只需要在兩條鏈表頭部各占一個位置也就是把邊節(jié)點的兩個link分別指向原來的頭節(jié)點然后更新頂點表里的firstedge。為什么這里可以放心地讓p-jlink指向G-adjmulist[j].firstedge即使j和i不是同一個頂點因為這條邊節(jié)點有兩個獨立的指針槽位分別掛兩邊互不干擾。ilink和jlink各自只對自己負(fù)責(zé)的那條鏈表負(fù)責(zé)不存在一條鏈表占兩個指針的問題。3.2 打印鄰接信息和遍歷一條邊的規(guī)則打印是檢驗結(jié)構(gòu)是否正確的試金石。根據(jù)前面說的判斷規(guī)則打印某個頂點的所有鄰居代碼可以這樣寫void PrintAdjList(AMLGraph *G) { for (int i 0; i G-vexnum; i) { printf(頂點 %c 的鄰接頂點: , G-adjmulist[i].data); EBox *p G-adjmulist[i].firstedge; while (p) { int another (p-ivex i) ? p-jvex : p-ivex; printf(%c , G-adjmulist[another].data); // 關(guān)鍵根據(jù)當(dāng)前頂點在邊節(jié)點中的位置決定走 ilink 還是 jlink p (p-ivex i) ? p-ilink : p-jlink; } printf(\n); } }這里有一個容易忽略的細(xì)節(jié)頂點 i 和邊節(jié)點 p 的關(guān)系不是固定的。同一條邊在頂點 X 的鏈表里走的是ilink或jlink到了頂點 Y 那里可能就要換另一個指針。所以遍歷時每次都要先判斷“當(dāng)前頂點是該邊的ivex還是jvex”然后再決定下一步往哪個方向前進。如果你用鄰接表養(yǎng)成了習(xí)慣拿到一個節(jié)點就直接p p-next在鄰接多重表里會踩大坑。因為這里的節(jié)點本身沒有單一的 next 指針強行只走ilink或只走jlink都會把頂點自己的鏈表走斷或者繞到別的頂點的鏈表里去。3.3 刪除一條邊解鏈過程才是重頭戲刪除邊是鄰接多重表優(yōu)勢最明顯的地方因為物理上只需要釋放一個節(jié)點。但代碼依然要小心必須同時把這條邊從兩個頂點的鏈表中摘下來。void RemoveEdge(AMLGraph *G, int i, int j) { EBox **pp1 G-adjmulist[i].firstedge; EBox *target NULL; // 第一趟在頂點 i 的鏈表中找到目標(biāo)邊并解除鏈接 while (*pp1) { EBox *cur *pp1; if ((cur-ivex i cur-jvex j) || (cur-ivex j cur-jvex i)) { // 跳過當(dāng)前節(jié)點把它從 i 的鏈表中摘除 *pp1 (cur-ivex i) ? cur-ilink : cur-jlink; target cur; break; } pp1 (cur-ivex i) ? cur-ilink : cur-jlink; } if (target NULL) { printf(邊 (%d, %d) 不存在\n, i, j); return; } // 第二趟在頂點 j 的鏈表中找到同一個節(jié)點并解除鏈接 EBox **pp2 G-adjmulist[j].firstedge; while (*pp2) { EBox *cur *pp2; if (cur target) { *pp2 (cur-ivex j) ? cur-jlink : cur-ilink; break; } pp2 (cur-ivex j) ? cur-jlink : cur-ilink; } free(target); target NULL; G-edgenum--; }我故意用了二級指針EBox **而不只是一級指針。因為在單向鏈表里刪除當(dāng)前節(jié)點需要修改前驅(qū)節(jié)點的指向要么你保存前驅(qū)節(jié)點要么用二級指針直接指向“前驅(qū)節(jié)點里存當(dāng)前位置的那個成員”。二級指針寫出來的代碼簡潔得多而且不會漏掉頭節(jié)點被刪除時firstedge需要更新的情況。刪除的時候還有一個細(xì)節(jié)在頂點 i 的鏈表中找到了目標(biāo)節(jié)點后保存到target再退出去第二趟。第二趟不能用第一趟里同樣的判斷去“重新找一條邊”因為如果你重新用 (i, j) 去匹配萬一有重邊兩次匹配到的可能是不同的邊節(jié)點。正確做法是直接比較指針地址cur target找到物理上的那個節(jié)點這才是同一條邊。這里順便提一句復(fù)雜度刪除一條邊需要沿著頂點 i 的鏈表找到目標(biāo)再沿著頂點 j 的鏈表找到目標(biāo)最壞情況下是 O(degree(i) degree(j))。這個復(fù)雜度和鄰接表是一樣的但因為物理上只有一個節(jié)點需要釋放而且不需要維護兩個邊節(jié)點之間的配對關(guān)系代碼的出錯率明顯低很多。4. 用一張五頂點圖把整個過程跑一遍4.1 從零開始建一張圖觀察鏈表形態(tài)先別急著寫復(fù)雜算法咱們用一個具體例子手動捋一遍鄰接多重表的“生長過程”。現(xiàn)在有一張無向圖頂點分別是 A、B、C、D、E邊集合如下A 和 B 之間有一條邊A 和 C 之間有一條邊C 和 D 之間有一條邊B 和 D 之間有一條邊B 和 E 之間有一條邊我用邊節(jié)點e1到e5來給每一條邏輯邊編號方便描述。用頭插法依次把邊放進圖里注意新插入的邊總會出現(xiàn)在鏈表頭部。插入 e1(A, B) 之后頂點 A 的邊鏈表e1頂點 B 的邊鏈表e1插入 e2(A, C) 之后頂點 A 的邊鏈表e2 - e1頂點 C 的邊鏈表e2現(xiàn)在想一想從頂點 A 出發(fā)遍歷鏈表e2 節(jié)點的ivex是 Ajvex是 C因為 A 對應(yīng)的是ivex所以下一步走ilink正好指向 e1。e1 的ivex是 Ajvex是 B再走ilink走到空。這樣 A 的鄰居依次是 C、B和插入順序正好相反。這說明頭插法會反轉(zhuǎn)鄰接順序?qū)懰惴〞r不要假定鏈表的順序和輸入順序一致。插入 e3(C, D) 之后頂點 C 的邊鏈表e3 - e2頂點 D 的邊鏈表e3頂點 C 的鏈表遍歷就很有代表性了從 e3 開始e3 的ivex是 Cjvex是 D所以走ilink到 e2e2 的ivex是 Ajvex是 C當(dāng)前頂點 C 對應(yīng)的是jvex所以這一步要切換方向走jlink。很多人第一次手推鏈表時就是在這里斷掉的明明 e2 里有 next 指針為什么走到 NULL 了因為他沒意識到頂點 C 的鏈表是靠jlink串起來的而不是ilink。插入 e4(B, D) 和 e5(B, E) 之后整個圖的邊鏈形態(tài)如下頂點 A 的邊鏈表e2 - e1頂點 B 的邊鏈表e5 - e4 - e1頂點 C 的邊鏈表e3 - e2頂點 D 的邊鏈表e4 - e3頂點 E 的邊鏈表e5頂點 B 獲取鄰接頂點的過程是先看 e5e5 的ivex是 B另一個端點是 E走ilink到 e4e4 的ivex是 B另一個端點是 D走ilink到 e1e1 的ivex是 Ajvex是 B當(dāng)前頂點 B 對應(yīng)的是jvex所以走jlink走到空。于是 B 的鄰居枚舉結(jié)果是 E、D、A。注意五條邊在物理上只有五個節(jié)點分別存入兩個頂點的鏈表中。這就是邏輯上共享、物理上獨立的意思。4.2 刪除邊之后的鏈表變化接著上面的例子現(xiàn)在刪除邊 (B, D)也就是 e4。調(diào)用RemoveEdge(G, 1, 3)假設(shè) B 的下標(biāo)是 1D 的下標(biāo)是 3。第一趟在頂點 B 的鏈表中找鏈表是 e5 - e4 - e1。走到 e4 時匹配成功把 B 的firstedge鏈路上的e4摘掉改成 e4 - e1這里更準(zhǔn)確地說是把 e5 的ilink直接從 e4 改到 e1因為 e5 的ivex是 B走的是ilink。于是頂點 B 的鏈表變成 e5 - e1。第二趟在頂點 D 的鏈表中找。D 的鏈表原本是 e4 - e3。e4 是鏈表頭直接在 D 的firstedge上做修改因為 e4 的jvex是 D所以走的是jlink于是 D 的firstedge被改成 e4 原來的jlink也就是 e3。最終 D 的鏈表變成 e3。然后free(e4)這一步之后物理內(nèi)存里就真的沒有 e4 了。從這張圖里再想找 B 和 D 之間的邊遍歷 B 或者 D 的鏈表都找不到。這個例子也說明了鄰接多重表的刪除操作天然做到了“同步”不需要像鄰接表那樣在兩個獨立節(jié)點上分別做釋放只要在兩條鏈表上做一次解鏈再釋放一次內(nèi)存圖的邏輯結(jié)構(gòu)就依然完整。而且整個過程只需要一個target指針保存目標(biāo)節(jié)點不用擔(dān)心兩個鏈表拿到的節(jié)點不一致。5. 三種存儲放一起比一比表里見真章5.1 復(fù)雜度與適用場景對比很多同學(xué)背了一堆定義真到選存儲結(jié)構(gòu)時反而不會選。用一張對比表把鄰接矩陣、鄰接表、鄰接多重表放在一起看存儲結(jié)構(gòu)空間復(fù)雜度判斷兩頂點是否相鄰刪除一條無向邊遍歷所有邊鄰接矩陣O(n2)O(1)直接查下標(biāo)O(1)改兩個數(shù)組元素O(n2)需要掃整個矩陣鄰接表O(ne)O(min(degree(i), degree(j)))需走鏈表O(degree(i)degree(j))釋放兩個節(jié)點O(ne)但無向圖每條邊會被數(shù)兩遍需要去重鄰接多重表O(ne)O(min(degree(i), degree(j)))規(guī)律相同O(degree(i)degree(j))只釋放一個節(jié)點O(ne)每條邊物理上只有一個節(jié)點天然不重復(fù)先解釋“判斷兩頂點是否相鄰”這一行。鄰接表里要判斷 i 和 j 是否相連可以從 i 的鏈表里找 j也可以從 j 的鏈表里找 i哪邊鏈表短從哪邊走所以是min(degree(i), degree(j))的量級。鄰接多重表也是一樣的邏輯只是遍歷時多了個判斷“當(dāng)前端點走 ilink 還是 jlink”的步驟常數(shù)更大一點但復(fù)雜度級別沒變。再解釋“遍歷所有邊”這一行這是很多書的對比表里不寫但實際算法里特別關(guān)鍵的一項。鄰接多重表因為一條邊只有一個邊節(jié)點遍歷所有邊時直接順著某個順序把所有邊節(jié)點過一遍即可天然不會重復(fù)。而在鄰接表中如果 DFS 無向圖時要枚舉所有邊會因為每條邊都存了兩遍必須用 mark 數(shù)組或者類似機制避免重復(fù)枚舉多一層負(fù)擔(dān)。空間上鄰接表和鄰接多重表都是 O(ne)但鄰接表在無向圖中要建 2e 個邊節(jié)點鄰接多重表只需要 e 個邊節(jié)點每個節(jié)點多一個指針域。如果 e 很大鄰接多重表省下來的節(jié)點頭身部分還是很可觀的。5.2 有向圖就用十字鏈表別硬套說到這可能會有人問那有向圖能不能用鄰接多重表嚴(yán)格來說有向圖的“弧”是有方向的一條弧從起點發(fā)出到終點結(jié)束。如果非要用鄰接多重表就得把每一條弧的兩個端點看成ivex和jvex這樣“出邊”和“入邊”都會串在同一個邊節(jié)點上。但你將無法區(qū)分這條弧到底是從 ivex 指向 jvex還是反過來因為鄰接多重表的邊本來就是無向的節(jié)點里根本沒保存方向信息。有向圖更適合用十字鏈表。十字鏈表給每個弧節(jié)點也設(shè)置了兩個指針一個指向“同一起點的下一條弧”一個指向“同一終點的下一條弧”頂點節(jié)點則分別維護“第一條出邊”和“第一條入邊”。這個結(jié)構(gòu)和鄰接多重表神似只是把無向邊的兩個端點換成了弧的弧尾和弧頭方向信息被編碼進去。所以如果要做一個“有向圖 邊操作頻繁”的需求直接學(xué)十字鏈表如果是“無向圖 需要對邊進行增刪改查”的需求鄰接多重表就是正統(tǒng)答案。常見考試題或者課程設(shè)計里出現(xiàn)“用鄰接多重表實現(xiàn)無向圖的 DFS/BFS 或最小生成樹”本質(zhì)都是因為它適合反復(fù)處理邊而不只是查看頂點鄰居。6. 邊界情況與寫代碼的常見坑6.1 自環(huán)和重邊會讓默認(rèn)寫法“翻車”前面所有代碼都有個隱含假設(shè)插入的邊連接的是兩個不同頂點也就是i ! j。但現(xiàn)實里圖是可以有自環(huán)邊的比如一個頂點有一條邊直接連回自己。這種情況下如果還照抄上面的插入函數(shù)會出現(xiàn)一個隱蔽的錯誤。假設(shè)在頂點 5 插入一條自環(huán)邊 (5, 5)按代碼邏輯p-ivex 5; p-jvex 5; p-ilink G-adjmulist[5].firstedge; G-adjmulist[5].firstedge p; p-jlink G-adjmulist[5].firstedge; // 此時 firstedge 已經(jīng)是 p 了問題就出在最后一行G-adjmulist[5].firstedge已經(jīng)被更新成了 p所以p-jlink指向了它自身形成一個自環(huán)指針。下次遍歷頂點 5 的邊鏈表時走到 p 之后判斷ivex 5成立走ilink如果原來有邊還能繼續(xù)走但如果再判斷另一個端點jvex 5也成立走jlink就會走回自己陷入死循環(huán)。處理辦法也很簡單插入邊之前先判斷if (i j) { // 自環(huán)只接入一份鏈表或者單獨設(shè)計結(jié)構(gòu) p-ilink G-adjmulist[i].firstedge; G-adjmulist[i].firstedge p; return; }不過絕大多數(shù)考研和課程要求的鄰接多重表默認(rèn)討論的是沒有自環(huán)的圖所以這個邊界經(jīng)常被一筆帶過。你寫代碼時一定要自己想清楚如果數(shù)據(jù)輸入里出現(xiàn)了自環(huán)程序怎么處理才不會掛。重邊則剛好相反平行邊在鄰接多重表里是完全安全的。插入兩條同樣的邊 (i, j)它們會生成兩個不同的邊節(jié)點各自掛到 i 和 j 的鏈表中。遍歷時兩個鄰居都打印出來刪除時也只會刪掉匹配到的第一條剩下的那條依然存在。所以如果題目的圖允許重邊鄰接多重表反而比鄰接矩陣更自然因為鄰接矩陣用 0/1 根本表達(dá)不了“同時存在兩條邊”的狀態(tài)還得改成計數(shù)矩陣。6.2 手寫鄰接多重表的幾個好習(xí)慣我見過不少同學(xué)上機寫鄰接多重表代碼邏輯看著沒問題一運行就段錯誤排查半天發(fā)現(xiàn)都是小事。這里分享幾個我自己的習(xí)慣希望你也能少走彎路。第一個習(xí)慣是malloc出來的邊節(jié)點一定要把所有指針初始化為NULL。這看起來是老生常談但在鄰接多重表里格外重要。因為一個邊節(jié)點有兩個指針如果你只給其中一個賦值另一個忘了初始化它就是一個野指針。遍歷時一旦走到那里程序立刻崩潰。第二個習(xí)慣是寫遍歷代碼時把“判斷當(dāng)前頂點等于 ivex 還是 jvex”提煉成一個變量不要到處散落判斷語句。比如int current i; int next (p-ivex current) ? p-ilink : p-jlink;這樣寫的好處是遇到邏輯復(fù)雜的地方不容易看錯分支。如果直接在每一處都寫p-ivex i ? ...代碼量大時特別容易把ivex和jvex寫反。第三個習(xí)慣是刪除邊或頂點的算法最好先畫一張小圖把鏈表形態(tài)寫出來再動筆寫代碼。不少同學(xué)圖省事直接對著結(jié)構(gòu)體開始寫寫完以后鏈表到底連成什么樣完全沒數(shù)出了問題也只能干瞪眼。鄰接多重表的調(diào)試難點在于一個指針同時屬于兩條鏈表打印某個頂點的鄰接信息根本無法直觀看出整個結(jié)構(gòu)是否完整。最好的辦法是寫一個小的可視化函數(shù)把每條邊的兩個端點和它的ilink、jlink指向都打印出來void DebugPrintEdges(AMLGraph *G) { for (int v 0; v G-vexnum; v) { EBox *p G-adjmulist[v].firstedge; printf(頂點 %d 的邊鏈表: , v); while (p) { int other (p-ivex v) ? p-jvex : p-ivex; printf((%d,%d) , p-ivex, other); p (p-ivex v) ? p-ilink : p-jlink; } printf(\n); } }調(diào)試時先打印確認(rèn)每條鏈表都符合你手推的結(jié)果再繼續(xù)寫上層算法。這個過程在很多教材里被略過了但它確實是最能培養(yǎng)圖結(jié)構(gòu)手感的一步。說到最后鄰接多重表可能不如鄰接矩陣那樣一眼就能看懂也不像鄰接表那樣在任何圖算法里都能通用但它對“無向圖的邊操作”這個場景的優(yōu)化是實打?qū)嵉?。我自己的體會是當(dāng)你需要寫一個不停增刪邊、遍歷邊、給邊打標(biāo)記的算法時鄰接多重表會幫你省掉大量“處理重復(fù)節(jié)點”的臟活讓你把注意力集中在算法本身上這也是它能在諸多圖的存儲結(jié)構(gòu)里占一席之地的真正原因。 鄰接多重表：無向圖邊操作高效存儲結(jié)構(gòu)精講
1. 鄰接表在無向圖里為什么“存邊”存得別扭1.1 鄰接表的基本思路只有兩句話學(xué)圖存儲結(jié)構(gòu)時大多數(shù)人最先接觸的是鄰接矩陣和鄰接表。鄰接矩陣的思路很好理解開一個 n×n 的二維數(shù)組arc[i][j]為 1 就表示 i 到 j 之間有一條邊為 0 就沒有。判斷兩個頂點是否鄰接查一次數(shù)組下標(biāo)就完成了O(1) 的代價非常痛快。但它的短板也擺在明面上空間是 O(n2) 的頂點一多比如 5000 個頂點的稀疏圖光矩陣就要吃掉 25,000,000 個存儲單元大部分還是 0純屬浪費。鄰接表于是做了改進用“每個頂點掛一條鏈表”的方式把每個頂點的鄰接頂點串起來。每個頂點只需要一個頭節(jié)點再加若干條邊節(jié)點總空間降到了 O(ne)。這個思路簡潔、直覺所以幾乎所有教材都會把它當(dāng)作圖存儲的重點來講。但鄰接表解決的是“從一個頂點出發(fā)能找到哪些鄰居”的問題。一旦問題的對象從頂點換成邊鄰接表就開始露怯了。尤其是無向圖一條邊會被保存兩次從頂點 A 的角度看它有一條邊連向 B從頂點 B 的角度看它有一條邊連向 A。這聽起來不過是多存了一次但如果要做“刪除一條邊”“給一條邊打訪問標(biāo)記”“遍歷所有邊但每條邊只處理一次”這類操作麻煩就來了。1.2 “刪邊”在鄰接表里的連鎖反應(yīng)咱們用一個簡單例子推演一下。無向圖里有邊 (A, B)在鄰接表中必然存在兩個邊節(jié)點一個掛在 A 的鏈表里數(shù)據(jù)是 B一個掛在 B 的鏈表里數(shù)據(jù)是 A?，F(xiàn)在想讓這條邊消失程序至少要干四件事在 A 的鏈表中找到 B 的節(jié)點修改前驅(qū)節(jié)點的 next 指針釋放這個節(jié)點在 B 的鏈表中找到 A 的節(jié)點再次修改前驅(qū)節(jié)點的 next 指針再釋放一個節(jié)點。要注意的是這兩個節(jié)點雖然描述的是同一條邏輯邊但物理上完全是兩個獨立的內(nèi)存對象。如果只是在 A 那邊刪了B 那邊還掛著一個指向 A 的節(jié)點圖的狀態(tài)就錯了。更難受的是遍歷所有邊這種極其常見的需求在無向圖鄰接表里天然會把每條邊數(shù)兩遍你得額外加一個 visited 標(biāo)記或者設(shè)計去重邏輯寫起來特別容易漏。我把這種別扭總結(jié)成一句話鄰接表把“邊”這個對象拆成了兩份然后讓所有基于邊的操作都得先做一次‘去重’或‘同步’。鄰接多重表的出現(xiàn)就是專門為了避免這份別扭而設(shè)計的它在結(jié)構(gòu)上保證一條邊在物理上只出現(xiàn)一次邏輯上卻能同時掛在兩個頂點下面。這種存儲方式在無向圖里尤其是對邊頻繁操作的算法里比鄰接表又要舒服一個量級。2. 鄰接多重表的節(jié)點設(shè)計一條邊一個對象2.1 節(jié)點里的五個字段是干什么的先把結(jié)構(gòu)體的 C 語言定義擺出來這是理解鄰接多重表的骨架#define MAX_VERTEX_NUM 20 typedef struct EBox { int mark; // 標(biāo)記該邊是否被訪問過常用于遍歷 int ivex, jvex; // 該邊依附的兩個頂點在頂點表中的下標(biāo) struct EBox *ilink; // 指向下一條依附于頂點 ivex 的邊 struct EBox *jlink; // 指向下一條依附于頂點 jvex 的邊 int info; // 邊的權(quán)值普通圖可以不使用 } EBox; typedef struct VexBox { char data; // 頂點自身的值 EBox *firstedge; // 指向第一條依附于該頂點的邊 } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; } AMLGraph;看到這個結(jié)構(gòu)很多人的第一反應(yīng)是這不就是鄰接表嗎確實頂點表部分很像但邊節(jié)點部分是質(zhì)的區(qū)別。在鄰接表里邊節(jié)點里只有一個指針next指向下一個鄰接頂點在鄰接多重表里邊節(jié)點里有兩個指針ilink和jlink分別服務(wù)于邊的兩個端點。ivex和jvex存的是邊的兩個端點下標(biāo)沒有方向誰前誰后無所謂只要一條邊的兩端信息完整即可。ilink的含義是“指向下一條依附于 ivex 這個頂點的邊”jlink的含義是“指向下一條依附于 jvex 這個頂點的邊”。這兩個指針不是冗余備份而是各管一攤分別讓這條邊能夠同時掛進兩個頂點的鏈表中。mark字段像是給這條邊準(zhǔn)備的便簽紙。由于無向圖的邊天然沒有方向遍歷或搜索時如果不做標(biāo)記非常容易把同一條邊當(dāng)成兩條邊來訪問。有了mark你可以用它記錄“這條邊我已經(jīng)處理過了”算法跑一遍下來邊的訪問狀態(tài)清清楚楚。info字段則用來存權(quán)值比如邊的長度或代價需要用網(wǎng)圖時就有地方放了。2.2 五個字段如何撐起兩個并行的邊鏈表比較微妙的地方在于鄰接多重表里每個頂點依然有一條屬于自己的邊鏈表但鏈表里的節(jié)點是共享的。舉個例子無向圖有一條邊連接頂點 0 和頂點 3。創(chuàng)建這條邊時分配一個邊節(jié)點令ivex 0jvex 3。然后把這個節(jié)點同時插入到頂點 0 的邊鏈表中也插入到頂點 3 的邊鏈表中。也就是說這個物理節(jié)點同時出現(xiàn)在兩條鏈表中但它只占一份內(nèi)存。頂點 0 在遍歷自己的鄰接邊時怎么從當(dāng)前邊走到下一條邊呢必須判斷當(dāng)前節(jié)點里哪個下標(biāo)是 0。如果ivex 0就沿著ilink往下走否則說明 0 存在jvex里就沿著jlink往下走。同理從頂點 3 出發(fā)遍歷時也用同樣的判斷規(guī)則從ivex或者jvex中識別自己然后選擇對應(yīng)的鏈接。這種設(shè)計的本質(zhì)是把“這條邊在兩個頂點各自鏈表里的 next 指針”合并進了同一個邊節(jié)點。在鄰接表里一個邊對象存在于兩個獨立節(jié)點中同步維護它們之間的聯(lián)系只靠前驅(qū)節(jié)點。在鄰接多重表中一條邊只有一個節(jié)點但它帶著兩個指針分別通向它在兩個頂點鏈表里的下一條邊。因此你在任何一個頂點的鏈表里看到的都是一個完整的邊節(jié)點而不是一個殘缺的“鄰居編號”。實際寫代碼時最容易踩的坑就是這個判斷流程。很多初學(xué)者以為ilink永遠(yuǎn)是“左端點方向的下一跳”jlink永遠(yuǎn)是“右端點方向的下一跳”結(jié)果圖一建出來遍歷各種亂跳。要記住ilink只管ivex這個端點jlink只管jvex這個端點你可以把每個邊節(jié)點想象成一個十字路口兩個方向各有一條路需要去哪個端點就往哪個方向拐。3. 手寫鄰接多重表初始化、加邊、遍歷、刪邊3.1 初始化和插入邊的完整實現(xiàn)了解了結(jié)構(gòu)定義下一步就直接寫代碼。下面是一個可以直接跑起來的最小實現(xiàn)包含四個核心函數(shù)初始化圖、插入邊、打印每個頂點的鄰接信息、刪除邊。#include stdio.h #include stdlib.h #define MAX_VERTEX_NUM 20 typedef struct EBox { int mark; int ivex, jvex; struct EBox *ilink; struct EBox *jlink; int info; } EBox; typedef struct VexBox { char data; EBox *firstedge; } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; } AMLGraph; void InitGraph(AMLGraph *G, int vexnum) { G-vexnum vexnum; G-edgenum 0; for (int i 0; i vexnum; i) { G-adjmulist[i].firstedge NULL; } } void InsertEdge(AMLGraph *G, int i, int j) { EBox *p (EBox *)malloc(sizeof(EBox)); p-mark 0; p-ivex i; p-jvex j; p-info 0; // 將新邊插入頂點 i 的邊鏈表頭部 p-ilink G-adjmulist[i].firstedge; G-adjmulist[i].firstedge p; // 將同一條邊插入頂點 j 的邊鏈表頭部 p-jlink G-adjmulist[j].firstedge; G-adjmulist[j].firstedge p; G-edgenum; }插入邊用的是頭插法也就是每次都把新邊放到鏈表的第一個位置。頭插的好處是實現(xiàn)簡單不用維護尾指針。由于每個頂點都有自己的鏈表新邊只需要在兩條鏈表頭部各占一個位置也就是把邊節(jié)點的兩個link分別指向原來的頭節(jié)點然后更新頂點表里的firstedge。為什么這里可以放心地讓p-jlink指向G-adjmulist[j].firstedge即使j和i不是同一個頂點因為這條邊節(jié)點有兩個獨立的指針槽位分別掛兩邊互不干擾。ilink和jlink各自只對自己負(fù)責(zé)的那條鏈表負(fù)責(zé)不存在一條鏈表占兩個指針的問題。3.2 打印鄰接信息和遍歷一條邊的規(guī)則打印是檢驗結(jié)構(gòu)是否正確的試金石。根據(jù)前面說的判斷規(guī)則打印某個頂點的所有鄰居代碼可以這樣寫void PrintAdjList(AMLGraph *G) { for (int i 0; i G-vexnum; i) { printf(頂點 %c 的鄰接頂點: , G-adjmulist[i].data); EBox *p G-adjmulist[i].firstedge; while (p) { int another (p-ivex i) ? p-jvex : p-ivex; printf(%c , G-adjmulist[another].data); // 關(guān)鍵根據(jù)當(dāng)前頂點在邊節(jié)點中的位置決定走 ilink 還是 jlink p (p-ivex i) ? p-ilink : p-jlink; } printf(\n); } }這里有一個容易忽略的細(xì)節(jié)頂點 i 和邊節(jié)點 p 的關(guān)系不是固定的。同一條邊在頂點 X 的鏈表里走的是ilink或jlink到了頂點 Y 那里可能就要換另一個指針。所以遍歷時每次都要先判斷“當(dāng)前頂點是該邊的ivex還是jvex”然后再決定下一步往哪個方向前進。如果你用鄰接表養(yǎng)成了習(xí)慣拿到一個節(jié)點就直接p p-next在鄰接多重表里會踩大坑。因為這里的節(jié)點本身沒有單一的 next 指針強行只走ilink或只走jlink都會把頂點自己的鏈表走斷或者繞到別的頂點的鏈表里去。3.3 刪除一條邊解鏈過程才是重頭戲刪除邊是鄰接多重表優(yōu)勢最明顯的地方因為物理上只需要釋放一個節(jié)點。但代碼依然要小心必須同時把這條邊從兩個頂點的鏈表中摘下來。void RemoveEdge(AMLGraph *G, int i, int j) { EBox **pp1 G-adjmulist[i].firstedge; EBox *target NULL; // 第一趟在頂點 i 的鏈表中找到目標(biāo)邊并解除鏈接 while (*pp1) { EBox *cur *pp1; if ((cur-ivex i cur-jvex j) || (cur-ivex j cur-jvex i)) { // 跳過當(dāng)前節(jié)點把它從 i 的鏈表中摘除 *pp1 (cur-ivex i) ? cur-ilink : cur-jlink; target cur; break; } pp1 (cur-ivex i) ? cur-ilink : cur-jlink; } if (target NULL) { printf(邊 (%d, %d) 不存在\n, i, j); return; } // 第二趟在頂點 j 的鏈表中找到同一個節(jié)點并解除鏈接 EBox **pp2 G-adjmulist[j].firstedge; while (*pp2) { EBox *cur *pp2; if (cur target) { *pp2 (cur-ivex j) ? cur-jlink : cur-ilink; break; } pp2 (cur-ivex j) ? cur-jlink : cur-ilink; } free(target); target NULL; G-edgenum--; }我故意用了二級指針EBox **而不只是一級指針。因為在單向鏈表里刪除當(dāng)前節(jié)點需要修改前驅(qū)節(jié)點的指向要么你保存前驅(qū)節(jié)點要么用二級指針直接指向“前驅(qū)節(jié)點里存當(dāng)前位置的那個成員”。二級指針寫出來的代碼簡潔得多而且不會漏掉頭節(jié)點被刪除時firstedge需要更新的情況。刪除的時候還有一個細(xì)節(jié)在頂點 i 的鏈表中找到了目標(biāo)節(jié)點后保存到target再退出去第二趟。第二趟不能用第一趟里同樣的判斷去“重新找一條邊”因為如果你重新用 (i, j) 去匹配萬一有重邊兩次匹配到的可能是不同的邊節(jié)點。正確做法是直接比較指針地址cur target找到物理上的那個節(jié)點這才是同一條邊。這里順便提一句復(fù)雜度刪除一條邊需要沿著頂點 i 的鏈表找到目標(biāo)再沿著頂點 j 的鏈表找到目標(biāo)最壞情況下是 O(degree(i) degree(j))。這個復(fù)雜度和鄰接表是一樣的但因為物理上只有一個節(jié)點需要釋放而且不需要維護兩個邊節(jié)點之間的配對關(guān)系代碼的出錯率明顯低很多。4. 用一張五頂點圖把整個過程跑一遍4.1 從零開始建一張圖觀察鏈表形態(tài)先別急著寫復(fù)雜算法咱們用一個具體例子手動捋一遍鄰接多重表的“生長過程”。現(xiàn)在有一張無向圖頂點分別是 A、B、C、D、E邊集合如下A 和 B 之間有一條邊A 和 C 之間有一條邊C 和 D 之間有一條邊B 和 D 之間有一條邊B 和 E 之間有一條邊我用邊節(jié)點e1到e5來給每一條邏輯邊編號方便描述。用頭插法依次把邊放進圖里注意新插入的邊總會出現(xiàn)在鏈表頭部。插入 e1(A, B) 之后頂點 A 的邊鏈表e1頂點 B 的邊鏈表e1插入 e2(A, C) 之后頂點 A 的邊鏈表e2 - e1頂點 C 的邊鏈表e2現(xiàn)在想一想從頂點 A 出發(fā)遍歷鏈表e2 節(jié)點的ivex是 Ajvex是 C因為 A 對應(yīng)的是ivex所以下一步走ilink正好指向 e1。e1 的ivex是 Ajvex是 B再走ilink走到空。這樣 A 的鄰居依次是 C、B和插入順序正好相反。這說明頭插法會反轉(zhuǎn)鄰接順序?qū)懰惴〞r不要假定鏈表的順序和輸入順序一致。插入 e3(C, D) 之后頂點 C 的邊鏈表e3 - e2頂點 D 的邊鏈表e3頂點 C 的鏈表遍歷就很有代表性了從 e3 開始e3 的ivex是 Cjvex是 D所以走ilink到 e2e2 的ivex是 Ajvex是 C當(dāng)前頂點 C 對應(yīng)的是jvex所以這一步要切換方向走jlink。很多人第一次手推鏈表時就是在這里斷掉的明明 e2 里有 next 指針為什么走到 NULL 了因為他沒意識到頂點 C 的鏈表是靠jlink串起來的而不是ilink。插入 e4(B, D) 和 e5(B, E) 之后整個圖的邊鏈形態(tài)如下頂點 A 的邊鏈表e2 - e1頂點 B 的邊鏈表e5 - e4 - e1頂點 C 的邊鏈表e3 - e2頂點 D 的邊鏈表e4 - e3頂點 E 的邊鏈表e5頂點 B 獲取鄰接頂點的過程是先看 e5e5 的ivex是 B另一個端點是 E走ilink到 e4e4 的ivex是 B另一個端點是 D走ilink到 e1e1 的ivex是 Ajvex是 B當(dāng)前頂點 B 對應(yīng)的是jvex所以走jlink走到空。于是 B 的鄰居枚舉結(jié)果是 E、D、A。注意五條邊在物理上只有五個節(jié)點分別存入兩個頂點的鏈表中。這就是邏輯上共享、物理上獨立的意思。4.2 刪除邊之后的鏈表變化接著上面的例子現(xiàn)在刪除邊 (B, D)也就是 e4。調(diào)用RemoveEdge(G, 1, 3)假設(shè) B 的下標(biāo)是 1D 的下標(biāo)是 3。第一趟在頂點 B 的鏈表中找鏈表是 e5 - e4 - e1。走到 e4 時匹配成功把 B 的firstedge鏈路上的e4摘掉改成 e4 - e1這里更準(zhǔn)確地說是把 e5 的ilink直接從 e4 改到 e1因為 e5 的ivex是 B走的是ilink。于是頂點 B 的鏈表變成 e5 - e1。第二趟在頂點 D 的鏈表中找。D 的鏈表原本是 e4 - e3。e4 是鏈表頭直接在 D 的firstedge上做修改因為 e4 的jvex是 D所以走的是jlink于是 D 的firstedge被改成 e4 原來的jlink也就是 e3。最終 D 的鏈表變成 e3。然后free(e4)這一步之后物理內(nèi)存里就真的沒有 e4 了。從這張圖里再想找 B 和 D 之間的邊遍歷 B 或者 D 的鏈表都找不到。這個例子也說明了鄰接多重表的刪除操作天然做到了“同步”不需要像鄰接表那樣在兩個獨立節(jié)點上分別做釋放只要在兩條鏈表上做一次解鏈再釋放一次內(nèi)存圖的邏輯結(jié)構(gòu)就依然完整。而且整個過程只需要一個target指針保存目標(biāo)節(jié)點不用擔(dān)心兩個鏈表拿到的節(jié)點不一致。5. 三種存儲放一起比一比表里見真章5.1 復(fù)雜度與適用場景對比很多同學(xué)背了一堆定義真到選存儲結(jié)構(gòu)時反而不會選。用一張對比表把鄰接矩陣、鄰接表、鄰接多重表放在一起看存儲結(jié)構(gòu)空間復(fù)雜度判斷兩頂點是否相鄰刪除一條無向邊遍歷所有邊鄰接矩陣O(n2)O(1)直接查下標(biāo)O(1)改兩個數(shù)組元素O(n2)需要掃整個矩陣鄰接表O(ne)O(min(degree(i), degree(j)))需走鏈表O(degree(i)degree(j))釋放兩個節(jié)點O(ne)但無向圖每條邊會被數(shù)兩遍需要去重鄰接多重表O(ne)O(min(degree(i), degree(j)))規(guī)律相同O(degree(i)degree(j))只釋放一個節(jié)點O(ne)每條邊物理上只有一個節(jié)點天然不重復(fù)先解釋“判斷兩頂點是否相鄰”這一行。鄰接表里要判斷 i 和 j 是否相連可以從 i 的鏈表里找 j也可以從 j 的鏈表里找 i哪邊鏈表短從哪邊走所以是min(degree(i), degree(j))的量級。鄰接多重表也是一樣的邏輯只是遍歷時多了個判斷“當(dāng)前端點走 ilink 還是 jlink”的步驟常數(shù)更大一點但復(fù)雜度級別沒變。再解釋“遍歷所有邊”這一行這是很多書的對比表里不寫但實際算法里特別關(guān)鍵的一項。鄰接多重表因為一條邊只有一個邊節(jié)點遍歷所有邊時直接順著某個順序把所有邊節(jié)點過一遍即可天然不會重復(fù)。而在鄰接表中如果 DFS 無向圖時要枚舉所有邊會因為每條邊都存了兩遍必須用 mark 數(shù)組或者類似機制避免重復(fù)枚舉多一層負(fù)擔(dān)。空間上鄰接表和鄰接多重表都是 O(ne)但鄰接表在無向圖中要建 2e 個邊節(jié)點鄰接多重表只需要 e 個邊節(jié)點每個節(jié)點多一個指針域。如果 e 很大鄰接多重表省下來的節(jié)點頭身部分還是很可觀的。5.2 有向圖就用十字鏈表別硬套說到這可能會有人問那有向圖能不能用鄰接多重表嚴(yán)格來說有向圖的“弧”是有方向的一條弧從起點發(fā)出到終點結(jié)束。如果非要用鄰接多重表就得把每一條弧的兩個端點看成ivex和jvex這樣“出邊”和“入邊”都會串在同一個邊節(jié)點上。但你將無法區(qū)分這條弧到底是從 ivex 指向 jvex還是反過來因為鄰接多重表的邊本來就是無向的節(jié)點里根本沒保存方向信息。有向圖更適合用十字鏈表。十字鏈表給每個弧節(jié)點也設(shè)置了兩個指針一個指向“同一起點的下一條弧”一個指向“同一終點的下一條弧”頂點節(jié)點則分別維護“第一條出邊”和“第一條入邊”。這個結(jié)構(gòu)和鄰接多重表神似只是把無向邊的兩個端點換成了弧的弧尾和弧頭方向信息被編碼進去。所以如果要做一個“有向圖 邊操作頻繁”的需求直接學(xué)十字鏈表如果是“無向圖 需要對邊進行增刪改查”的需求鄰接多重表就是正統(tǒng)答案。常見考試題或者課程設(shè)計里出現(xiàn)“用鄰接多重表實現(xiàn)無向圖的 DFS/BFS 或最小生成樹”本質(zhì)都是因為它適合反復(fù)處理邊而不只是查看頂點鄰居。6. 邊界情況與寫代碼的常見坑6.1 自環(huán)和重邊會讓默認(rèn)寫法“翻車”前面所有代碼都有個隱含假設(shè)插入的邊連接的是兩個不同頂點也就是i ! j。但現(xiàn)實里圖是可以有自環(huán)邊的比如一個頂點有一條邊直接連回自己。這種情況下如果還照抄上面的插入函數(shù)會出現(xiàn)一個隱蔽的錯誤。假設(shè)在頂點 5 插入一條自環(huán)邊 (5, 5)按代碼邏輯p-ivex 5; p-jvex 5; p-ilink G-adjmulist[5].firstedge; G-adjmulist[5].firstedge p; p-jlink G-adjmulist[5].firstedge; // 此時 firstedge 已經(jīng)是 p 了問題就出在最后一行G-adjmulist[5].firstedge已經(jīng)被更新成了 p所以p-jlink指向了它自身形成一個自環(huán)指針。下次遍歷頂點 5 的邊鏈表時走到 p 之后判斷ivex 5成立走ilink如果原來有邊還能繼續(xù)走但如果再判斷另一個端點jvex 5也成立走jlink就會走回自己陷入死循環(huán)。處理辦法也很簡單插入邊之前先判斷if (i j) { // 自環(huán)只接入一份鏈表或者單獨設(shè)計結(jié)構(gòu) p-ilink G-adjmulist[i].firstedge; G-adjmulist[i].firstedge p; return; }不過絕大多數(shù)考研和課程要求的鄰接多重表默認(rèn)討論的是沒有自環(huán)的圖所以這個邊界經(jīng)常被一筆帶過。你寫代碼時一定要自己想清楚如果數(shù)據(jù)輸入里出現(xiàn)了自環(huán)程序怎么處理才不會掛。重邊則剛好相反平行邊在鄰接多重表里是完全安全的。插入兩條同樣的邊 (i, j)它們會生成兩個不同的邊節(jié)點各自掛到 i 和 j 的鏈表中。遍歷時兩個鄰居都打印出來刪除時也只會刪掉匹配到的第一條剩下的那條依然存在。所以如果題目的圖允許重邊鄰接多重表反而比鄰接矩陣更自然因為鄰接矩陣用 0/1 根本表達(dá)不了“同時存在兩條邊”的狀態(tài)還得改成計數(shù)矩陣。6.2 手寫鄰接多重表的幾個好習(xí)慣我見過不少同學(xué)上機寫鄰接多重表代碼邏輯看著沒問題一運行就段錯誤排查半天發(fā)現(xiàn)都是小事。這里分享幾個我自己的習(xí)慣希望你也能少走彎路。第一個習(xí)慣是malloc出來的邊節(jié)點一定要把所有指針初始化為NULL。這看起來是老生常談但在鄰接多重表里格外重要。因為一個邊節(jié)點有兩個指針如果你只給其中一個賦值另一個忘了初始化它就是一個野指針。遍歷時一旦走到那里程序立刻崩潰。第二個習(xí)慣是寫遍歷代碼時把“判斷當(dāng)前頂點等于 ivex 還是 jvex”提煉成一個變量不要到處散落判斷語句。比如int current i; int next (p-ivex current) ? p-ilink : p-jlink;這樣寫的好處是遇到邏輯復(fù)雜的地方不容易看錯分支。如果直接在每一處都寫p-ivex i ? ...代碼量大時特別容易把ivex和jvex寫反。第三個習(xí)慣是刪除邊或頂點的算法最好先畫一張小圖把鏈表形態(tài)寫出來再動筆寫代碼。不少同學(xué)圖省事直接對著結(jié)構(gòu)體開始寫寫完以后鏈表到底連成什么樣完全沒數(shù)出了問題也只能干瞪眼。鄰接多重表的調(diào)試難點在于一個指針同時屬于兩條鏈表打印某個頂點的鄰接信息根本無法直觀看出整個結(jié)構(gòu)是否完整。最好的辦法是寫一個小的可視化函數(shù)把每條邊的兩個端點和它的ilink、jlink指向都打印出來void DebugPrintEdges(AMLGraph *G) { for (int v 0; v G-vexnum; v) { EBox *p G-adjmulist[v].firstedge; printf(頂點 %d 的邊鏈表: , v); while (p) { int other (p-ivex v) ? p-jvex : p-ivex; printf((%d,%d) , p-ivex, other); p (p-ivex v) ? p-ilink : p-jlink; } printf(\n); } }調(diào)試時先打印確認(rèn)每條鏈表都符合你手推的結(jié)果再繼續(xù)寫上層算法。這個過程在很多教材里被略過了但它確實是最能培養(yǎng)圖結(jié)構(gòu)手感的一步。說到最后鄰接多重表可能不如鄰接矩陣那樣一眼就能看懂也不像鄰接表那樣在任何圖算法里都能通用但它對“無向圖的邊操作”這個場景的優(yōu)化是實打?qū)嵉?。我自己的體會是當(dāng)你需要寫一個不停增刪邊、遍歷邊、給邊打標(biāo)記的算法時鄰接多重表會幫你省掉大量“處理重復(fù)節(jié)點”的臟活讓你把注意力集中在算法本身上這也是它能在諸多圖的存儲結(jié)構(gòu)里占一席之地的真正原因。