【數據結構】圖論存儲結構深度解析：鄰接多重表如何實現無向圖O(1)刪邊？鄰接矩陣/鏈表/十字鏈對比

鄰接多重表

導讀
一、有向圖的存儲結構
二、鄰接多重表
三、存儲結構
四、算法評價
- 4.1 時間復雜度
- 4.2 空間復雜度
五、四種存儲方式的總結
- 5.1 空間復雜度
- 5.2 找相鄰邊
- 5.3 刪除邊或結點
- 5.4 適用于
- 5.5 表示方式
六、圖的基本操作
結語

鄰接多重表

導讀

大家好，很高興又和大家見面啦！！！

經過前面的內容，我們已經學習了圖的三種存儲結構：

鄰接矩陣
鄰接表
十字鏈表

在今天的內容中我們將會介紹圖的第四種存儲結構以及圖的一些基本操作。下面我們直接進入今天的內容；

一、有向圖的存儲結構

在有向圖中，我們可以通過3種存儲結構來存儲有向圖的頂點與弧的信息，并且這三種存儲結構各有其優缺點：

鄰接矩陣
- 優點：能高效查找兩個頂點之間的邊，適合存儲稠密圖
- 不足：會浪費大量的存儲空間
鄰接表
- 優點：通過鏈式存儲大大節省了存儲空間，適合存儲稀疏圖
- 不足：邊的查找效率低下
十字鏈表
- 優點：提高了弧的查找效率，節省了存儲空間
- 不足：十字鏈表只能存儲有向圖

相較于鄰接矩陣與鄰接表，十字鏈表不僅提高了弧的查找效率，還節省了存儲空間。

但是十字鏈表法并不能像鄰接矩陣和鄰接表一樣不僅可以存儲有向圖，還可以存儲無向圖，十字鏈表法只能夠存儲有向圖。

那對于無向圖而言，有沒有一種存儲結構既能夠提高邊的查找效率，又能夠節省存儲空間呢？

二、鄰接多重表

在鄰接表中，容易求得頂點和邊的各種信息，但求兩個頂點之間是否存在邊兒執行刪除邊等操作時，需要分別在兩個頂點的邊表中遍歷，效率低。

鄰接多重表（Adjacency Multilist??）是無向圖的一種鏈式存儲結構。與十字鏈表類似，在鄰接多重表中，每條邊用一個結點表示，其結構如下所示：

其中：

ivex與jvex中存儲的是該邊依附的兩個頂點編號；
ilink 指向的時依附于頂點 i 的下一條邊
jlink 指向的時依附于頂點 j 的下一條邊
info 中存放的時該邊的相關信息，如邊的權值

每個頂點也用一個結點表示，它由兩個域組成：

data 域存放該頂點的相關信息
firstedge 域指向的時依附于該頂點的第一條邊

在鄰接多重表中，所有依附于同一頂點的邊串聯在同一鏈表中，因為每條邊依附于兩個頂點，所以每個邊結點同時鏈接在兩個鏈表中。

在無向圖中，其鄰接表與鄰接多重表的差別在于——同一條邊在兩個表中的結點數量不同：

鄰接表中，同一條邊用兩個結點表示
鄰接多重表中，只用一個結點表示

三、存儲結構

鄰接多重表的存儲結構中，同樣需要定義兩種結點類型：

#define MAXSIZE 5
typedef int Edge_ElemType;				// 邊信息數據類型
typedef int Vert_ElemType;				// 頂點信息數據類型
typedef struct Edge_Node {int ivex;							// 頂點i的編號int jvex;							// 頂點j的編號struct Edge_Node* ilink, * jlink;	// 依附于頂點i與頂點j的邊Edge_ElemType info;					// 邊的信息
}ENode;									// 邊結點
typedef struct VertexNode {Vert_ElemType data;					// 頂點信息ENode* firstedge;					// 依附于頂點的第一條邊的結點
}VNode;									// 頂點結點
typedef struct Adjacency_Multilist?? {VNode vert_list[MAXSIZE];			// 頂點表int edge_num;						// 邊的數量int vert_num;						// 頂點數量
}AMGraph;								// 鄰接多重表

當圖中的邊沒有權值時，可以省略邊結點中的info域；

四、算法評價

鄰接多重表的算法評價同樣以鄰接多重表的遍歷進行評價；

4.1 時間復雜度

在鄰接多重表中，遍歷所有頂點就是遍歷一個順序表，對于頂點數為 $∣ V ∣$ 的圖，其時間復雜度為 $O (∣ V ∣)$ ；

遍歷所有邊只需要將每一條邊都遍歷一次，對于邊數為 $∣ E ∣$ 的圖，其時間復雜度為 $∣ E ∣$ ；

整個圖的遍歷對應的時間復雜度為 $T (N) = O (∣ V ∣ + ∣ E ∣)$ ；

4.2 空間復雜度

在鄰接多重表中，對于頂點數為 $∣ V ∣$ ，邊數為 $∣ E ∣$ 的圖而言，其需要的空間復雜度為 $T (N) = O (∣ V ∣ + ∣ E ∣)$ ；

五、四種存儲方式的總結

下面我們會從五個維度來探討這四種存儲方式：

5.1 空間復雜度

在鄰接矩陣中，對于結點數為 $n$ 的圖，不管是有向圖還是無向圖都需要申請 $n^2$ 的空間，因此其空間復雜度均為 $n^2$ ；

在鄰接表中，對于結點數為 $∣ V ∣$ 和邊數為 $∣ E ∣$ 的圖，在有向圖和無向圖中，其空間復雜度并不相同：

有向圖中，需要申請 $∣ V ∣$ 個結點空間和 $∣ E ∣$ 個邊空間，因此對應的空間復雜度為： $O (∣ V ∣ + ∣ E ∣)$ ；
無向圖中，需要申請 $∣ V ∣$ 個結點空間和 $2 ? ∣ E ∣$ 個邊空間，因此對應的空間復雜度為： $O (∣ V ∣ + 2∣ E ∣)$ ；

在十字鏈表中，對于結點數為 $∣ V ∣$ 和邊數為 $∣ E ∣$ 的圖，需要申請同等數量的結點空間和邊空間，其對應的空間復雜度為： $O (∣ V ∣ + ∣ E ∣)$ ；

在鄰接多重表中，對于結點數為 $∣ V ∣$ 和邊數為 $∣ E ∣$ 的圖，需要申請同等數量的結點空間和邊空間，其對應的空間復雜度為： $O (∣ V ∣ + ∣ E ∣)$ ；

5.2 找相鄰邊

在鄰接矩陣中，當我們要查找一個頂點的相鄰邊時，我們只需要遍歷該頂點對應的行或者列。在鄰接矩陣中，行數與列數都是圖的頂點數 $∣ V ∣$ ，因此對應的時間復雜度為 $O (∣ V ∣)$ ；

在鄰接表中，當我們要查找一個頂點的相鄰邊時，對于有向圖與無向圖而言，其查找鄰邊的時間復雜度也是有所區別：

無向圖中，鄰接表查找鄰邊時，只需要遍歷該結點所指向的邊表即可
有向圖中，鄰接表查找鄰邊時，對于出度與入度的時間復雜度也是有區別：
- 出度：查找一個頂點的出度，只需要遍歷該結點所指向的邊表即可
- 入度：查找一個頂點的入度，需要遍歷整個鄰接表

在十字鏈表中，當我們要查找一個頂點的相鄰邊時，就是查找該頂點的出度與入度，這時只需要分別遍歷該結點的出度表與入度表即可

在鄰接多重表中，當我們要查找一個頂點的相鄰邊時，只需要遍歷對應的結點所鄰接的邊表即可

5.3 刪除邊或結點

在鄰接矩陣中：

當我們要刪除一條邊時，只需要修改對應邊在矩陣中的值即可
當我們要刪除一個頂點時，需要移動大量的數據

在鄰接表中：

有向圖：
- 刪除邊：只需要刪除對應的邊結點即可
- 刪除頂點：需要刪除與該結點相鄰的所有邊結點以及該頂點
無向圖：
- 刪除邊：需要刪除其依附的兩個頂點所對應的邊表中的邊結點
- 刪除頂點：需要刪除與該結點相鄰的所有邊結點以及該頂點

在十字鏈表和鄰接多重表中：

刪除邊：我們只需要刪除其對應的邊結點即可
刪除頂點：需要刪除與該頂點相鄰的所有邊結點以及該頂點信息

不難發現，在圖中，當我們要刪除一個頂點時，實際上就是需要查找該頂點相鄰邊并進行刪除，因此其刪除操作是基于查找操作實現；

5.4 適用于

鄰接矩陣由于需要消耗大量的空間用于存儲邊，因此適用于存儲稠密圖；

在鄰接表中，由于邊表是通過鏈表實現，能夠節省存儲空間，因此對于稀疏圖而言，更加適合用鄰接表進行存儲；

在十字鏈表中，只能夠存儲有向圖

在鄰接多重表中，只能夠存儲無向圖

5.5 表示方式

鄰接矩陣是由各個頂點組成的矩陣，因此，其表示方式是唯一的；

在鄰接表、十字鏈表以及鄰接多重表中，由于邊表的信息是通過鏈表進行的存儲，因此其邊表的表示方式并不唯一；

六、圖的基本操作

圖的基本操作時獨立于圖的存儲結構的。而對于不同的存儲方式，操作算法的具體實現會有著不同的性能。在設計具體算法的實現時，應考慮采用何種存儲方式的算法效率會更高。

圖的基本操作主要包括：

Adjacent(G, x, y): 判斷圖G是否存在邊<x, y>或(x, y)；
Neighbors(G, x): 列出圖G中與結點x鄰接的邊
InsertVertex(G, x): 在圖G中插入頂點x
DeleteVertex(G, x): 在圖G中刪除頂點x
AddEdge(G, x, y): 若無向邊(x, y)或有向邊<x, y>不存在，則向圖G中添加改邊
RemoveEdge(G, x, y): 若無向邊(x, y)或有向邊<x, y>存在，則從圖G中刪除該邊
FirstNeighbors(G, x): 求圖G中頂點x的第一個鄰接點，若有則返回頂點號。若x沒有鄰接點或圖中不存在x，則返回-1
NextNeighbors(G, x, y): 假設圖G中頂點 y 是頂點 x 的一個鄰接點，返回除 y 外頂點 x 的下一個鄰接點的頂點號，若 y 是 x 的最后一個鄰接點，則返回-1
Get_edge_value(G, x, y): 獲取圖G中邊(x, y) 或 <x, y> 對應的權值
Set_edge_value(G, x, y, v): 設置圖G中邊(x, y) 或 <x, y> 對應的權值

此外，還有圖的遍歷算法：按照某種方式訪問圖中的每個頂點，且僅訪問一次。圖的遍歷算法有兩種：

深度優先遍歷（Depth-First-Search, DFS）
廣度優先遍歷（Breadth-First-Search, BFS）

具體內容會在下一個篇章中進行介紹。

結語

鄰接多重表以“單邊雙鏈”的革新設計，將無向圖的存儲效率推向新高度——空間占用減半、刪邊操作躍升至??O(1)??，完美解決了鄰接表的冗余與低效痛點。

從鄰接矩陣的剛性布局到鏈式結構的動態靈動，每一種存儲方案都是空間與時間的精妙權衡，而??鄰接多重表無疑是高頻刪邊場景的無向圖終極答案??。

??但存儲結構只是圖算法的起點??，真正的挑戰在于如何基于這些結構實現高效操作。??下一篇將深入圖的廣度優先遍歷（BFS）??，解析其在鄰接矩陣、鄰接表及鄰接多重表中的性能差異，并揭秘如何通過存儲優化讓BFS在千萬級節點圖中依然游刃有余！

🔍 ??本文是否為你撥開了圖存儲的迷霧？??
👍 ??點贊??支持原創深度干貨，讓技術洞察傳播更遠！
📁 ??收藏??構建你的圖論知識庫，開發實戰隨時查閱。
🔄 ??轉發??至技術社區，與同行探討存儲選型與算法優化。
💬 評論區??留下你的疑問??：你在BFS實現中遇到過哪些性能瓶頸？我們共同拆解！
🔔 ??關注追蹤更新??，《圖的廣度優先遍歷：從理論到超大規模實戰》即將上線！

🚀 ??技術進階之路，我們并肩前行！?