Appearance
十字链表与邻接多重表
核心思想
十字链表（有向图）
十字链表的核心思路是为每个弧建立一个弧结点，同时将它链入两条链表——以该弧的弧头顶点为头的链表和以弧尾顶点为头的链表，形成"十字"交叉结构。
弧结点结构：
| 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)
邻接多重表
结构定义（C 语言）：
c
typedef struct EdgeNode {
bool mark; // 访问标志（边级别，遍历时用）
int ivex, jvex; // 边的两个端点编号
struct EdgeNode *ilink; // 依附于 ivex 的下一条边
struct EdgeNode *jlink; // 依附于 jvex 的下一条边
// InfoType *info; // 权值等信息（可选）
} EdgeNode;
typedef struct {
VertexType data;
EdgeNode *firstedge; // 第一条依附于该顶点的边
} VexNode;
VexNode adjMulList[MAXV];建立邻接多重表：
- 创建顶点数组，将每个顶点的
firstedge初始化为 NULL - 对每条边
(Vi, Vj)，创建一个边结点，设置ivex=i、jvex=j - 将边结点用头插法插入 Vi 的边链表（通过 ilink）和 Vj 的边链表（通过 jlink）
手画示例（这是理解"一个结点挂两条链"的关键）：
无向图有 4 个顶点、4 条边，按 e1=(0,1)、e2=(0,2)、e3=(1,2)、e4=(2,3) 的顺序头插建表，四条顶点链如下（∧ 表示 NULL）：
V0.firstedge → e2(0,2) ─ilink→ e1(0,1) ─ilink→ ∧
V1.firstedge → e3(1,2) ─ilink→ e1(0,1) ─jlink→ ∧
V2.firstedge → e4(2,3) ─ilink→ e3(1,2) ─jlink→ e2(0,2) ─jlink→ ∧
V3.firstedge → e4(2,3) ─jlink→ ∧注意两点：① 全图只有 4 个边结点（邻接表要 8 个）；② 同一个结点 e1 既在 V0 的链上又在 V1 的链上——从 V0 进来时 V0 是它的 ivex 端，沿 ilink 走；从 V1 进来时 V1 是它的 jvex 端，沿 jlink 走。走哪条链取决于"当前顶点是这条边的哪一端"，这是邻接多重表所有操作的统一套路：
c
// 遍历依附于顶点 v 的所有边（通用模板）
for (EdgeNode *p = adjMulList[v].firstedge; p != NULL;
p = (p->ivex == v) ? p->ilink : p->jlink) {
// 处理边 p，对端顶点 = (p->ivex == v) ? p->jvex : p->ivex
}删除边操作：
邻接多重表删除边 (Vi, Vj) 只需把同一个结点从两条链上分别摘除，再 free 一次：
c
// 把边结点 e 从顶点 v 的边链表中摘除
void detach(int v, EdgeNode *e) {
EdgeNode *p = adjMulList[v].firstedge, *pre = NULL;
while (p != e) { // 找 e 在 v 链中的前驱
pre = p;
p = (p->ivex == v) ? p->ilink : p->jlink;
}
EdgeNode *next = (e->ivex == v) ? e->ilink : e->jlink;
if (pre == NULL)
adjMulList[v].firstedge = next; // e 是链头
else if (pre->ivex == v)
pre->ilink = next; // 前驱经 ilink 链到 e
else
pre->jlink = next; // 前驱经 jlink 链到 e
}
// 删除边 (i, j)
detach(i, e);
detach(j, e);
free(e); // 只 free 一次——这就是"删边只删一个结点"对比邻接表：邻接表中无向边 (Vi, Vj) 对应两个独立的边结点，删边要在两条链里分别找到并 free 两次，还要保证两边删干净不残留。
mark 标志位的作用：
需要对每条边只处理一次的操作（输出所有边、统计边权和、给每条边做标记）中，邻接多重表把 mark 置位即可——因为每条边本来就只有一个结点。邻接表里同一条边有两个分身，要么开一张额外的"边已处理"表，要么靠 i < j 之类的约定去重。
c
// 在邻接多重表上对每条边恰好处理一次（以 DFS 框架为例）
void DFS(int v) {
visited[v] = true; // 顶点标志照常要有
for (EdgeNode *p = adjMulList[v].firstedge; p != NULL;
p = (p->ivex == v) ? p->ilink : p->jlink) {
if (!p->mark) {
p->mark = true; // 这条边处理过了，另一端不再处理
int u = (p->ivex == v) ? p->jvex : p->ivex;
if (!visited[u]) DFS(u);
}
}
}易错：mark 是边的访问标志，不能代替顶点的
visited[]——两个标志各管各的：visited[]防止顶点重复访问，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 标志位的作用（偶尔考）
易错：十字链表只适用于有向图。对应地，无向图有邻接多重表——每条边只存一个结点（邻接表中无向边要存两次）。408 需要区分两者的适用场景。