十字链表与邻接多重表，有向图与无向图的高效链式存储结构解析

在图论的数据结构实现中，如何高效存储图并支持快速查询与动态修改，一直是算法设计的核心挑战。邻接表虽为最常用结构，但在特定场景下存在明显局限：对于有向图，仅用邻接表可快速得顶点出度，却需遍历全图才能统计入度；若改用逆邻接表，则入度易求而出度难获。无向图中，邻接表对同一条边在两个端点处重复存储，导致删除边时需同步修改两条链表，操作繁琐且易出错。

为解决上述问题，十字链表（Orthogonal List）与邻接多重表（Adjacency MultiList）应运而生，分别针对有向图与无向图提供更紧凑、更高效的链式表示方案。

十字链表：有向图的“双向索引”结构

十字链表本质是邻接表与逆邻接表的融合体，其核心思想是让每条弧（有向边）在逻辑上同时属于起点的出边链和终点的入边链，从而实现对出度与入度的即时访问。

其结点结构分为两类：

顶点结点：包含data（顶点信息）、firstin（指向该顶点入边链首结点）、firstout（指向该顶点出边链首结点）。
边结点：包含tailvex（弧起点下标）、headvex（弧终点下标）、taillink（指向同起点的下一条弧）、headlink（指向同终点的下一条弧），以及可选的info域（用于网的权值存储）。

如图1所示，左侧为有向图实例（A→B, A→C, B→C, C→A），右侧为对应十字链表的内存布局。每个顶点结点通过firstin与firstout分别挂载入边与出边链；每条边结点（如A→C）既被A的firstout链指向，又被C的firstin链指向，形成“十字交叉”结构——这也是其名称由来。

该结构的空间复杂度为O(|V| + |E|)，与邻接表一致；创建时间复杂度亦相同。关键优势在于：

查询任一顶点的出度或入度仅需遍历其单条链表，无需全局扫描；
边的插入/删除操作只需修改相关指针，逻辑清晰且不易遗漏；
特别适用于需频繁统计度数或进行拓扑排序等依赖入/出度信息的算法。

实际工程中，十字链表曾被用于高性能网络仿真与AOI（Area of Interest）区域同步系统。例如，在C++实现的二维AOI同步模块中，十字链表能高效维护玩家位置与可见区域的动态关联关系，避免因频繁增删导致的性能抖动。

邻接多重表：无向图的“边中心”设计

无向图中，边无方向性，邻接表将同一条边（如V0-V2）在V0与V2的邻接链中各存一次，造成冗余。当需删除该边时，必须分别在两个顶点的链表中定位并移除对应结点，效率低下且易出错。

邻接多重表通过“以边为中心”的设计彻底规避此问题：每条无向边仅用一个结点表示，并通过双链指针同时链接到其两端顶点的边链中。

其结点结构为：

顶点结点：含data与firstedge（指向第一条依附于该顶点的边）；
边结点：含ivex与jvex（边两端点下标）、ilink（指向依附于ivex的下一条边）、jlink（指向依附于jvex的下一条边），以及可选info域。

如图2所示，无向图（A-B, A-C, B-C）中，边A-B仅用一个边结点表示，其ivex=0（A）、jvex=1（B）；该结点同时被A的firstedge链与B的firstedge链引用。删除边A-B时，仅需调整该边结点的ilink与jlink指针，使其脱离两端顶点的边链即可，无需二次查找。

其空间复杂度同样为O(|V| + |E|)，但动态操作优势显著：

删除一条边仅需一次指针重连，时间复杂度O(1)；
删除一个顶点时，只需清空其firstedge所指的整个边链，其余边自动解绑；
边的遍历与合并操作更为自然，适合图的动态重构场景。

值得注意的是，邻接多重表并非万能：若算法主要关注顶点邻接关系（如DFS/BFS），邻接表仍具缓存局部性优势；而多重表因指针跳转更随机，可能影响CPU缓存命中率。因此，选择应基于具体操作模式权衡。

对比与适用场景

三者对比可归纳如下：

|--------------|------------|------------|------------|-------------|--------------|

| 邻接表 | 有向/无向 | O(|V|+|E|) | O(deg) | 出度快/入度慢（有向） | 通用图遍历、最短路径 |

| 十字链表 | 有向图 | O(|V|+|E|) | O(1) | 出度与入度均O(deg) | 拓扑排序、强连通分量、AOI同步 |

| 邻接多重表 | 无向图 | O(|V|+|E|) | O(1) | 度数查询O(deg) | 图编辑、动态网络、社交关系重构 |

| 边集数组 | 任意图 | O(|V|+|E|) | O(|E|) | 度数查询O(|E|) | Kruskal算法、边排序处理 |

边集数组（如图3所示）虽结构简单，但仅适合对边进行批量处理的场景（如最小生成树），因其无法高效支持顶点级查询或局部修改。

图3展示了一个带权有向图及其边集数组表示：顶点数组存储V0–V4，边数组每行记录begin、end与weight。该结构直观但低效，仅在边操作占主导时具优势。

工程实践中的取舍

在现代系统中，图数据结构的选择已不局限于理论最优。例如，大型图数据库（如Neo4j）底层采用混合存储：稠密子图用邻接矩阵加速，稀疏部分用变种邻接表；而实时游戏引擎中，AOI管理常定制十字链表变体，以平衡内存与更新延迟。

西北大学耿国华教授在《数据结构》课程中强调：“存储结构服务于操作需求，没有绝对优劣，只有是否匹配。”这一原则至今仍具指导意义。

随着图神经网络（GNN）兴起，对图的动态更新与子图采样提出更高要求，传统链式结构在分布式环境下面临扩展性瓶颈。但其清晰的逻辑模型与低层可控性，使其仍在嵌入式系统、高频交易网络等对延迟极度敏感的场景中不可替代。

综上，十字链表与邻接多重表作为经典链式图存储方案，通过精巧的指针设计解决了邻接表的固有缺陷，在需要高效边操作与度数统计的场景中持续发挥价值。理解其原理，有助于开发者在具体问题中做出更精准的结构选型。