十字链表与邻接多重表解决有向无向图存储痛点 提升边操作效率至O1

在图数据结构设计中，邻接表虽常用，但在有向图中难以同时高效获取顶点入度与出度，在无向图中同一条边需重复存储导致删除操作繁琐。为弥补缺陷，十字链表与邻接多重表成为关键优化方案。十字链表专用于有向图，融合邻接表与逆邻接表逻辑，每个顶点结点含firstin与firstout指针，边结点通过taillink与headlink分别链接同起点与同终点的后续弧，形成“十字交叉”结构。该结构下，任一顶点出入度查询仅需遍历单链，时间复杂度均为O(deg)，边插入删除仅需调整局部指针，实现O(1)级动态操作，适用于拓扑排序、AOI同步等依赖度数信息的场景。邻接多重表面向无向图，采用“边中心”设计：每条边仅用一个结点表示，通过ilink与jlink双链同时挂载于两端顶点的边链中，删除边时只需断开该结点的两个指针连接，无需跨顶点查找，同样达成O(1)删除效率；删除顶点时亦可快速解绑所有关联边。二者空间复杂度均为O(|V|+|E|)，与邻接表持平，但动态性能显著提升。对比边集数组（仅适合批量边处理如Kruskal算法），两类链式结构更适配高频增删改场景。工程实践中，如实时游戏引擎AOI模块常定制十字链表变体，而图数据库则倾向混合策略；选择核心依据仍是具体操作模式——当系统频繁统计度数或修改边关系时，十字链表与邻接多重表仍具不可替代优势。