數(shù)據(jù)結(jié)構(gòu)8——圖3，十字鏈表，鄰接多重表

---

---

前言

除了之前的鄰接矩陣和鄰接表

鄰接表不唯一，在有向圖中只記錄出度

逆鄰接表記錄入度

---

一、十字鏈表

表示稀疏有向圖
結(jié)合了鄰接表和逆鄰接表的思想
獲取頂點(diǎn)的出邊（從該頂點(diǎn)出發(fā)的邊）和入邊（指向該頂點(diǎn)的邊）

• 通過(guò)為每個(gè)頂點(diǎn)維護(hù)兩個(gè)鏈表來(lái)實(shí)現(xiàn)：一個(gè)鏈表用于存儲(chǔ)從該頂點(diǎn)出發(fā)的所有邊（出邊），另一個(gè)鏈表用于存儲(chǔ)到達(dá)該頂點(diǎn)的所有邊（入邊）。

結(jié)構(gòu)

十字鏈表中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)圖中的一條邊

• 頂點(diǎn)節(jié)點(diǎn)：包含頂點(diǎn)信息和兩個(gè)指針。一個(gè)指針指向該頂點(diǎn)的第一個(gè)出邊節(jié)點(diǎn)（如果有的話），另一個(gè)指針指向第一個(gè)入邊節(jié)點(diǎn)（通過(guò)某個(gè)其他頂點(diǎn)指向該頂點(diǎn)的邊）的表頭節(jié)點(diǎn)（這通常是一個(gè)啞節(jié)點(diǎn)或哨兵節(jié)點(diǎn)，用于簡(jiǎn)化插入和刪除操作）。

Data（數(shù)據(jù)域）：存儲(chǔ)頂點(diǎn)信息。
First In（第一入邊）：指向該頂點(diǎn)的第一條入邊。
First Out（第一出邊）：指向該頂點(diǎn)的第一條出邊。

• 邊節(jié)點(diǎn)：包含邊的信息（如權(quán)重）、一個(gè)指向起始頂點(diǎn)節(jié)點(diǎn)的指針、一個(gè)指向下一條出邊節(jié)點(diǎn)的指針（在同一起始頂點(diǎn)下），以及一個(gè)指向下一條入邊節(jié)點(diǎn)的指針（這些入邊都指向同一個(gè)終點(diǎn)頂點(diǎn)，但它們可能來(lái)自不同的起始頂點(diǎn)）。

Tail Vertex（弧尾）：表示邊的起點(diǎn)。
Head Vertex（弧頭）：表示邊的終點(diǎn)。
Head Link（頭鏈域）：指向與當(dāng)前弧頭相同的下一個(gè)節(jié)點(diǎn)（指向同一個(gè)終點(diǎn)的下一條邊）。
Tail Link（尾鏈域）：指向與當(dāng)前弧尾相同的下一個(gè)節(jié)點(diǎn)（從同一個(gè)起點(diǎn)出發(fā)的下一條邊）。
Info（信息域）：存儲(chǔ)該邊的相關(guān)信息，例如權(quán)重。

例子

考慮一個(gè)簡(jiǎn)單的有向圖，有以下頂點(diǎn)和邊：
頂點(diǎn)：A, B, C
邊：A -> B, A -> C, B -> C

頂點(diǎn)表：
A：First Out -> A -> B，First In -> None
B：First Out -> B -> C，First In -> A -> B
C：First Out -> None，First In -> A -> C

邊節(jié)點(diǎn)：
A -> B：
Tail Vertex: A
Head Vertex: B
Tail Link: 指向下一條從 A 出發(fā)的邊 A -> C
Head Link: 指向下一條指向 B 的邊 None
A -> C：
Tail Vertex: A
Head Vertex: C
Tail Link: None
Head Link: 指向下一條指向 C 的邊 B -> C
B -> C：
Tail Vertex: B
Head Vertex: C
Tail Link: None
Head Link: None

Vertex A:Out: A -> B, A -> CIn: 
Vertex B:Out: B -> CIn: A -> B
Vertex C:Out: In: A -> C, B -> C

復(fù)雜例子

頂點(diǎn)：A, B, C, D, E
邊：
A -> B
A -> C
A -> D
B -> C
B -> E
C -> D
C -> E
D -> E

上圖，按照上面簡(jiǎn)單例子的思路
先；列頂點(diǎn)，再列邊，然后連線

二、鄰接多重表（Adjacency Multilist）

每條邊只存儲(chǔ)一次，但是它會(huì)被鏈接到兩個(gè)頂點(diǎn)的鏈表中，這兩個(gè)頂點(diǎn)是邊的兩個(gè)端點(diǎn)。

• 把邊的兩個(gè)頂點(diǎn)存放在邊表結(jié)點(diǎn)中，所有依附于同一個(gè)頂點(diǎn)的邊串聯(lián)在同一鏈表中。由于每條邊依附于兩個(gè)頂點(diǎn)，則每個(gè)邊表結(jié)點(diǎn)同時(shí)鏈接在兩個(gè)鏈表中。

頂點(diǎn)表：存儲(chǔ)圖中的頂點(diǎn)信息，每個(gè)頂點(diǎn)元素包含兩個(gè)域：
data域：用于存放與頂點(diǎn)相關(guān)的信息，如頂點(diǎn)名稱或編號(hào)。
firstedge域（或類似指針）：指向依附于該頂點(diǎn)的第一條邊在邊表中的節(jié)點(diǎn)。

邊表：存儲(chǔ)圖中邊的信息，每個(gè)邊表節(jié)點(diǎn)包含多個(gè)域，常見(jiàn)的幾個(gè)域包括：
mark：標(biāo)志域，用于標(biāo)記該邊是否被訪問(wèn)過(guò)或進(jìn)行過(guò)其他特定操作。
ivex和jvex：分別存放該邊兩個(gè)頂點(diǎn)在頂點(diǎn)表中的位置（即下標(biāo)）。
info：信息域，對(duì)于帶權(quán)圖，可以存放邊的權(quán)值；對(duì)于無(wú)向圖，此域可省略。
ilink和jlink：分別指向下一條依附于頂點(diǎn)ivex和jvex的邊在邊表中的節(jié)點(diǎn)。

例子

考慮一個(gè)簡(jiǎn)單的無(wú)向圖，包含4個(gè)頂點(diǎn)和5條邊：
頂點(diǎn)：A, B, C, D
邊：
A-B
A-C
B-C
B-D
C-D

1. 創(chuàng)建頂點(diǎn)節(jié)點(diǎn)
   首先，為每個(gè)頂點(diǎn)創(chuàng)建一個(gè)頂點(diǎn)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含一個(gè)指向其鄰接邊鏈表的指針。

頂點(diǎn)節(jié)點(diǎn) A
頂點(diǎn)標(biāo)識(shí): A
邊鏈表頭指針: 指向A的鄰接邊鏈表的頭節(jié)點(diǎn)
.

頂點(diǎn)節(jié)點(diǎn) B
頂點(diǎn)標(biāo)識(shí): B
邊鏈表頭指針: 指向B的鄰接邊鏈表的頭節(jié)點(diǎn)
.
頂點(diǎn)節(jié)點(diǎn) C
頂點(diǎn)標(biāo)識(shí): C
邊鏈表頭指針: 指向C的鄰接邊鏈表的頭節(jié)點(diǎn)
.
頂點(diǎn)節(jié)點(diǎn) D
頂點(diǎn)標(biāo)識(shí): D
邊鏈表頭指針: 指向D的鄰接邊鏈表的頭節(jié)點(diǎn)

2. 創(chuàng)建邊節(jié)點(diǎn)
   為每條邊創(chuàng)建一個(gè)邊節(jié)點(diǎn)，每個(gè)邊節(jié)點(diǎn)包含以下信息：
   目標(biāo)頂點(diǎn): 目標(biāo)頂點(diǎn)的標(biāo)識(shí)或引用
   邊的權(quán)重（如果有）
   下一個(gè)邊節(jié)點(diǎn)的指針: 指向鏈表中的下一個(gè)邊節(jié)點(diǎn)

邊節(jié)點(diǎn) A-B
目標(biāo)頂點(diǎn): B
邊的權(quán)重: 無(wú)
下一個(gè)邊節(jié)點(diǎn)的指針: null（這是A的鏈表中的第一個(gè)邊節(jié)點(diǎn)）
.
邊節(jié)點(diǎn) A-C
目標(biāo)頂點(diǎn): C
邊的權(quán)重: 無(wú)
下一個(gè)邊節(jié)點(diǎn)的指針: null（這是A的鏈表中的第二個(gè)邊節(jié)點(diǎn)）
.
邊節(jié)點(diǎn) B-C
目標(biāo)頂點(diǎn): C
邊的權(quán)重: 無(wú)
下一個(gè)邊節(jié)點(diǎn)的指針: null（這是B的鏈表中的第一個(gè)邊節(jié)點(diǎn)）
.
邊節(jié)點(diǎn) B-D
目標(biāo)頂點(diǎn): D
邊的權(quán)重: 無(wú)
下一個(gè)邊節(jié)點(diǎn)的指針: null（這是B的鏈表中的第二個(gè)邊節(jié)點(diǎn)）
.
邊節(jié)點(diǎn) C-D
目標(biāo)頂點(diǎn): D
邊的權(quán)重: 無(wú)
下一個(gè)邊節(jié)點(diǎn)的指針: null（這是C的鏈表中的第一個(gè)邊節(jié)點(diǎn)）

3:. 更新鄰接表

頂點(diǎn) A：
將邊節(jié)點(diǎn) A-B 插入到A的鄰接邊鏈表中。
將邊節(jié)點(diǎn) A-C 插入到A的鄰接邊鏈表中。
鏈表順序?yàn)?A-B -> A-C。

頂點(diǎn) B：
將邊節(jié)點(diǎn) B-C 插入到B的鄰接邊鏈表中。
將邊節(jié)點(diǎn) B-D 插入到B的鄰接邊鏈表中。
鏈表順序?yàn)?B-C -> B-D。

頂點(diǎn) C：
將邊節(jié)點(diǎn) C-D 插入到C的鄰接邊鏈表中。
需要將邊節(jié)點(diǎn) A-C 插入到C的鄰接邊鏈表中。
鏈表順序?yàn)?C-D -> A-C。

頂點(diǎn) D：
D的鏈表為空，因?yàn)镈沒(méi)有指向其他節(jié)點(diǎn)的邊（在無(wú)向圖中，D的邊已經(jīng)在其他節(jié)點(diǎn)的鏈表中表示）。

4. 完整的鄰接多重表結(jié)構(gòu)

頂點(diǎn) A
邊鏈表: A-B -> A-C
頂點(diǎn) B
邊鏈表: B-C -> B-D
頂點(diǎn) C
邊鏈表: C-D -> A-C
頂點(diǎn) D
邊鏈表: 空

復(fù)雜的，上圖，

頂點(diǎn)：A, B, C, D, E, F
邊：
A-B
A-C
B-C
B-D
C-E
D-E
D-F
E-F
A-F

重復(fù)的邊不再建立節(jié)點(diǎn)，而是連接到之前的那個(gè)節(jié)點(diǎn)上