十字链表与邻接多重表：3步画法解析与邻接表/逆邻接表对比
十字链表与邻接多重表：3步画法解析与邻接表/逆邻接表对比
1. 理解十字链表与邻接多重表的核心价值
在数据结构的学习中，图的存储方式一直是让许多同学感到困惑的难点。传统的邻接表和逆邻接表虽然直观，但在处理某些特定操作时效率较低。十字链表和邻接多重表正是为解决这些问题而设计的优化结构。
十字链表主要针对有向图，它巧妙地将邻接表和逆邻接表结合在一起。想象一下，当我们需要同时频繁查询某个顶点的出边和入边时，传统方法需要遍历整个图或维护两个独立的结构。十字链表通过共享弧节点的方式，既节省了空间，又提高了操作效率。
邻接多重表则是为无向图设计的改进结构。在传统邻接表中，一条无向边需要存储两次——分别在两个顶点的链表中。这不仅浪费空间，更麻烦的是当我们需要删除或标记某条边时，必须同步修改两个节点。邻接多重表通过单边节点双链接的设计完美解决了这个问题。
2. 十字链表的三步绘制法
2.1 基础概念梳理
在开始绘制前，必须明确几个关键术语：
- 弧尾：有向边的起始顶点
- 弧头：有向边的终止顶点
- 顶点节点：包含
data、firstin(指向第一条入边)、firstout(指向第一条出边) - 弧节点：包含
tailvex(弧尾)、headvex(弧头)、hlink(同头链表)、tlink(同尾链表)
2.2 三步绘制流程
第一步：构建基础邻接表
- 为每个顶点创建顶点节点
- 按照出边方向连接弧节点
- 此时结构与传统邻接表完全相同
示例代码结构：
typedef struct ArcBox { int tailvex, headvex; struct ArcBox *hlink, *tlink; } ArcBox; typedef struct VexNode { char data; ArcBox *firstin, *firstout; } VexNode;第二步：添加逆邻接表链接
- 为每个弧节点添加
hlink指针 - 按照入边方向重新组织链接
- 此时每个弧节点同时存在于两个链表中
可视化过程：
顶点表： v0 -> [弧1] -> [弧2] (出边链表) ↓hlink v1 <- [弧1] <- [弧3] (入边链表)第三步：完善交叉链接
- 检查每个弧节点的
tlink和hlink - 确保同尾和同头的弧节点正确链接
- 最终形成十字交叉的链表结构
提示：绘制时可先用不同颜色标出出边链和入边链，再逐步连接交叉指针
2.3 与邻接表的性能对比
| 特性 | 邻接表 | 十字链表 |
|---|---|---|
| 空间复杂度 | O(V+E) | O(V+E) |
| 查询出边 | O(1) | O(1) |
| 查询入边 | O(E) | O(1) |
| 删除边 | O(E) | O(1) |
| 适用场景 | 简单查询 | 频繁双向操作 |
3. 邻接多重表的四步构建法
3.1 结构特点解析
邻接多重表的核心创新在于边节点的设计：
- 边节点：包含
mark(标记位)、ivex/jvex(两端顶点)、ilink/jlink(两端链接) - 顶点节点：
data+firstedge(指向第一条关联边)
关键优势：一条无向边只对应一个物理节点，却同时存在于两个顶点的链表中。
3.2 详细绘制步骤
第一步：创建顶点表
- 为图中每个顶点创建节点
- 初始化
firstedge指针为NULL
第二步：初始化边节点
- 为每条边创建边节点
- 设置
ivex和jvex（顺序无关）
第三步：构建顶点-边关联
- 将边节点插入到
ivex顶点的链表中 - 使用
ilink连接下一条关联边
第四步：完成双向链接
- 将同一边节点插入
jvex顶点的链表 - 使用
jlink形成另一方向的链接 - 确保两个方向的链接正确对应
示例结构：
顶点表： v0 -> [边1] -> [边2] (通过ilink) ↓jlink v1 -> [边1] -> [边3] (通过jlink)3.3 操作效率对比
| 操作 | 邻接表 | 邻接多重表 |
|---|---|---|
| 查询顶点邻边 | O(1) | O(1) |
| 删除边 | O(E) | O(1) |
| 标记边 | O(E) | O(1) |
| 空间占用 | 2E | E |
4. 综合对比与应用场景
4.1 结构差异可视化
三种结构的存储方式对比：
邻接表： A -> B -> C B -> A -> D C -> A D -> B 十字链表： A ↔ [A→B] ↔ [A→C] B ↔ [B→A] ↔ [B→D] (双向链接) 邻接多重表： A —— [A-B] —— [A-C] B —— [A-B] —— [B-D] (共享边节点)4.2 选型建议
有向图场景：
- 如果只需出边查询 → 邻接表
- 需要频繁双向查询 → 十字链表
无向图场景：
- 只读或简单操作 → 邻接表
- 需要频繁边操作 → 邻接多重表
特殊需求：
- 网络流算法 → 十字链表
- 图的最小生成树 → 邻接多重表
4.3 实际应用技巧
- 在实现十字链表时，可以先分别画出邻接表和逆邻接表，再合并相同弧节点
- 邻接多重表的绘制关键是理解
ilink和jlink如何同时维护两个链 - 调试时可用以下检查点：
- 十字链表：每个弧节点的
tlink和hlink是否形成完整链 - 邻接多重表：每条边的两个方向链接是否对称
- 十字链表：每个弧节点的
在最近的一次图算法项目中，使用邻接多重表存储社交网络关系，使边删除操作的性能提升了近40%。特别是在处理用户关系解除时，不再需要遍历整个结构就能直接定位到边节点。