Appearance
十字链表与邻接多重表
为什么需要十字链表与邻接多重表
邻接矩阵空间开销大（O(V²)），邻接表在有向图中求入度不方便（需遍历整个表），在无向图中每条边存储两次导致删边困难。为了解决这些痛点，引入了两种改进的存储结构：
- 十字链表（Orthogonal List）：针对有向图，将邻接表和逆邻接表"合二为一"，既能快速找出度也能快速找入度
- 邻接多重表（Adjacency Multilist）：针对无向图，每条边只用一个结点表示，解决了邻接表中同一条边存两次、删边操作困难的问题
408 考研中，这两种结构是图存储章节的重要补充，常以选择题形式考查其适用场景和结构特点。
核心思想
十字链表（有向图）
十字链表的核心思路是为每个弧建立一个弧结点，同时将它链入两条链表——以该弧的弧头顶点为头的链表和以弧尾顶点为头的链表，形成"十字"交叉结构。
弧结点结构：
| tailvex | headvex | hlink | tlink | info || 字段 | 含义 |
|---|---|
| tailvex | 弧尾顶点编号（起点） |
| headvex | 弧头顶点编号（终点） |
| hlink | 指向弧头相同的下一条弧 |
| tlink | 指向弧尾相同的下一条弧 |
| info | 弧的权值等信息（可选） |
顶点结点结构：
| data | firstin | firstout || 字段 | 含义 |
|---|---|
| data | 顶点数据 |
| firstin | 指向以该顶点为弧头的第一条弧（入弧） |
| firstout | 指向以该顶点为弧尾的第一条弧（出弧） |
结构示意（有向图：V₀→V₁, V₀→V₂, V₂→V₁）：
顶点数组
[0] V₀ firstin=NULL firstout → (0,1) → (0,2) → NULL (tlink 链)
[1] V₁ firstin → (0,1) → (2,1) → NULL (hlink 链) firstout=NULL
[2] V₂ firstin → (0,2) → NULL firstout → (2,1) → NULL沿 firstout + tlink 可遍历某顶点的所有出弧（求出度）；沿 firstin + hlink 可遍历某顶点的所有入弧（求入度）。
邻接多重表（无向图）
邻接多重表的核心思路是每条边只用一个边结点表示，该结点同时被它关联的两个顶点的链表共享。
边结点结构：
| mark | ivex | ilink | jvex | jlink | info || 字段 | 含义 |
|---|---|
| mark | 标志位，标记该边是否被访问过 |
| ivex | 边的一个顶点编号 |
| ilink | 指向依附于 ivex 的下一条边 |
| jvex | 边的另一个顶点编号 |
| jlink | 指向依附于 jvex 的下一条边 |
| info | 边的权值等信息（可选） |
顶点结点结构：
| data | firstedge |每个顶点存储一个 firstedge 指针，指向第一条依附于该顶点的边。
关键特点：同一个边结点出现在两个顶点的边链表中，删除一条边只需删除一个结点，比邻接表高效。
交互可视化
通过下方的交互动画，你可以逐步观察十字链表与邻接多重表的执行过程：
操作详解
十字链表
建立十字链表：
- 创建顶点数组，将每个顶点的
firstin和firstout初始化为 NULL - 对每条弧
<Vi, Vj>，创建弧结点，设置tailvex=i、headvex=j - 将弧结点用头插法分别插入 Vi 的出弧链表（tlink 链）和 Vj 的入弧链表（hlink 链）
求顶点度：
- 出度：沿
firstout出发，沿tlink遍历，计数即可 - 入度：沿
firstin出发，沿hlink遍历，计数即可 - 度 = 出度 + 入度
十字链表的优点：
- 既能方便地求出度，也能方便地求入度（邻接表只能方便求出度）
- 空间复杂度 O(V+E)，与邻接表相同
- 建立十字链表的时间复杂度为 O(V+E)
邻接多重表
建立邻接多重表：
- 创建顶点数组，将每个顶点的
firstedge初始化为 NULL - 对每条边
(Vi, Vj)，创建一个边结点，设置ivex=i、jvex=j - 将边结点用头插法插入 Vi 的边链表（通过 ilink）和 Vj 的边链表（通过 jlink）
删除边操作：
邻接多重表中删除边 (Vi, Vj) 只需要：
- 在 Vi 的边链表中找到该边结点并摘除（修改 ilink 指针）
- 在 Vj 的边链表中找到该边结点并摘除（修改 jlink 指针）
- 释放该边结点
对比邻接表，邻接表中删除一条边需要分别在两个顶点的链表中找到并删除两个不同的边结点，操作更繁琐。
mark 标志位的作用：
在图的遍历（如 DFS/BFS）中，需要标记边是否已被访问。邻接多重表的 mark 字段可以直接标记，而邻接表中同一条边对应两个结点，标记时需要额外处理。
复杂度分析
四种图存储结构对比
| 存储结构 | 适用图类型 | 空间复杂度 | 求度 | 判断边是否存在 | 删边 | 特点 |
|---|---|---|---|---|---|---|
| 邻接矩阵 | 有向图/无向图 | O(V²) | O(V) | O(1) | O(1) | 适合稠密图，空间浪费大 |
| 邻接表 | 有向图/无向图 | O(V+E) | 出度 O(1)遍历；入度需遍历整表 | O(V) | 需删两个结点（无向图） | 适合稀疏图 |
| 十字链表 | 有向图 | O(V+E) | 出度/入度均可快速求 | O(V) | O(V) | 邻接表 + 逆邻接表的结合 |
| 邻接多重表 | 无向图 | O(V+E) | O(度数) | O(V) | 只需删一个结点 | 每条边仅一个结点，删边方便 |
建表时间复杂度
| 存储结构 | 建表时间 |
|---|---|
| 邻接矩阵 | O(V² + E) |
| 邻接表 | O(V + E) |
| 十字链表 | O(V + E) |
| 邻接多重表 | O(V + E) |
考研高频考点
- ⭐ 十字链表适用于有向图，邻接多重表适用于无向图（选择题高频易混淆）
- ⭐ 十字链表弧结点的五个域：tailvex、headvex、hlink、tlink、info（结构辨析题）
- ⭐ 四种存储结构的适用场景和优缺点对比（选择题/简答题必考）
- ⭐ 邻接多重表中每条边只有一个结点，删边只需删一个结点（对比邻接表）
- 十字链表中求入度沿 firstin + hlink，求出度沿 firstout + tlink（概念题）
- 邻接多重表 mark 标志位的作用（偶尔考）