【数据结构】8——图3，十字链表，邻接多重表

数据结构8——图3，十字链表，邻接多重表

---

---

前言

除了之前的邻接矩阵和邻接表

邻接表不唯一，在有向图中只记录出度

逆邻接表记录入度

---

一、十字链表

表示稀疏有向图
结合了邻接表和逆邻接表的思想
获取顶点的出边（从该顶点出发的边）和入边（指向该顶点的边）

• 通过为每个顶点维护两个链表来实现：一个链表用于存储从该顶点出发的所有边（出边），另一个链表用于存储到达该顶点的所有边（入边）。

结构

十字链表中的每个节点对应图中的一条边

• 顶点节点：包含顶点信息和两个指针。一个指针指向该顶点的第一个出边节点（如果有的话），另一个指针指向第一个入边节点（通过某个其他顶点指向该顶点的边）的表头节点（这通常是一个哑节点或哨兵节点，用于简化插入和删除操作）。

Data（数据域）：存储顶点信息。
First In（第一入边）：指向该顶点的第一条入边。
First Out（第一出边）：指向该顶点的第一条出边。

• 边节点：包含边的信息（如权重）、一个指向起始顶点节点的指针、一个指向下一条出边节点的指针（在同一起始顶点下），以及一个指向下一条入边节点的指针（这些入边都指向同一个终点顶点，但它们可能来自不同的起始顶点）。

Tail Vertex（弧尾）：表示边的起点。
Head Vertex（弧头）：表示边的终点。
Head Link（头链域）：指向与当前弧头相同的下一个节点（指向同一个终点的下一条边）。
Tail Link（尾链域）：指向与当前弧尾相同的下一个节点（从同一个起点出发的下一条边）。
Info（信息域）：存储该边的相关信息，例如权重。

例子

考虑一个简单的有向图，有以下顶点和边：
顶点：A, B, C
边：A -> B, A -> C, B -> C

顶点表：
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

边节点：
A -> B：
Tail Vertex: A
Head Vertex: B
Tail Link: 指向下一条从 A 出发的边 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

复杂例子

顶点：A, B, C, D, E
边：
A -> B
A -> C
A -> D
B -> C
B -> E
C -> D
C -> E
D -> E

上图，按照上面简单例子的思路
先；列顶点，再列边，然后连线

二、邻接多重表（Adjacency Multilist）

每条边只存储一次，但是它会被链接到两个顶点的链表中，这两个顶点是边的两个端点。

• 把边的两个顶点存放在边表结点中，所有依附于同一个顶点的边串联在同一链表中。由于每条边依附于两个顶点，则每个边表结点同时链接在两个链表中。

顶点表：存储图中的顶点信息，每个顶点元素包含两个域：
data域：用于存放与顶点相关的信息，如顶点名称或编号。
firstedge域（或类似指针）：指向依附于该顶点的第一条边在边表中的节点。

边表：存储图中边的信息，每个边表节点包含多个域，常见的几个域包括：
mark：标志域，用于标记该边是否被访问过或进行过其他特定操作。
ivex和jvex：分别存放该边两个顶点在顶点表中的位置（即下标）。
info：信息域，对于带权图，可以存放边的权值；对于无向图，此域可省略。
ilink和jlink：分别指向下一条依附于顶点ivex和jvex的边在边表中的节点。

例子

考虑一个简单的无向图，包含4个顶点和5条边：
顶点：A, B, C, D
边：
A-B
A-C
B-C
B-D
C-D

1. 创建顶点节点
   首先，为每个顶点创建一个顶点节点，每个节点包含一个指向其邻接边链表的指针。

顶点节点 A
顶点标识: A
边链表头指针: 指向A的邻接边链表的头节点
.

顶点节点 B
顶点标识: B
边链表头指针: 指向B的邻接边链表的头节点
.
顶点节点 C
顶点标识: C
边链表头指针: 指向C的邻接边链表的头节点
.
顶点节点 D
顶点标识: D
边链表头指针: 指向D的邻接边链表的头节点

2. 创建边节点
   为每条边创建一个边节点，每个边节点包含以下信息：
   目标顶点: 目标顶点的标识或引用
   边的权重（如果有）
   下一个边节点的指针: 指向链表中的下一个边节点

边节点 A-B
目标顶点: B
边的权重: 无
下一个边节点的指针: null（这是A的链表中的第一个边节点）
.
边节点 A-C
目标顶点: C
边的权重: 无
下一个边节点的指针: null（这是A的链表中的第二个边节点）
.
边节点 B-C
目标顶点: C
边的权重: 无
下一个边节点的指针: null（这是B的链表中的第一个边节点）
.
边节点 B-D
目标顶点: D
边的权重: 无
下一个边节点的指针: null（这是B的链表中的第二个边节点）
.
边节点 C-D
目标顶点: D
边的权重: 无
下一个边节点的指针: null（这是C的链表中的第一个边节点）

3:. 更新邻接表

顶点 A：
将边节点 A-B 插入到A的邻接边链表中。
将边节点 A-C 插入到A的邻接边链表中。
链表顺序为 A-B -> A-C。

顶点 B：
将边节点 B-C 插入到B的邻接边链表中。
将边节点 B-D 插入到B的邻接边链表中。
链表顺序为 B-C -> B-D。

顶点 C：
将边节点 C-D 插入到C的邻接边链表中。
需要将边节点 A-C 插入到C的邻接边链表中。
链表顺序为 C-D -> A-C。

顶点 D：
D的链表为空，因为D没有指向其他节点的边（在无向图中，D的边已经在其他节点的链表中表示）。

4. 完整的邻接多重表结构

顶点 A
边链表: A-B -> A-C
顶点 B
边链表: B-C -> B-D
顶点 C
边链表: C-D -> A-C
顶点 D
边链表: 空

复杂的，上图，

顶点：A, B, C, D, E, F
边：
A-B
A-C
B-C
B-D
C-E
D-E
D-F
E-F
A-F

重复的边不再建立节点，而是连接到之前的那个节点上