1. 从邻接表到十字链表一个“有向”问题的诞生在数据结构的学习和工程实践中图的存储结构一直是个核心话题。我们最熟悉的莫过于邻接矩阵和邻接表。邻接矩阵直观但空间复杂度是O(n²)对于稀疏图简直是灾难。邻接表则灵活得多它用一个数组存储所有顶点每个顶点后面挂着一个链表链表的节点代表了从这个顶点出发的边。对于无向图邻接表很完美一条边会在两个顶点的链表中各出现一次空间复杂度O(VE)查找一个顶点的出边也很快。但当我们把目光投向有向图时邻接表的“小瑕疵”就暴露出来了。假设我们有一个描述微博关注关系的有向图顶点是用户一条从A指向B的边表示A关注了B。用邻接表存储我们很容易回答“A关注了哪些人”查A的出边链表。但如果产品经理问你“哪些人关注了B”即查找B的入边邻接表就尴尬了。你需要遍历所有顶点的链表才能找出那些指向B的边时间复杂度是O(VE)。这在顶点数巨大比如百万级用户时是无法接受的性能瓶颈。这就是十字链表法要解决的“有向”痛点。它不是一个凭空创造的全新结构而是对邻接表的一次精妙“升级”目标很明确在保留邻接表查找出边高效的前提下同样高效地支持查找入边。你可以把它理解为给邻接表的每个边节点加了“反向指针”让边与边之间形成了纵横交错的“十字”链接因此得名。理解十字链表不仅能帮你应对数据结构考试中关于图存储的各类变体题更能让你在设计涉及密集关系查询如社交网络、任务依赖分析、知识图谱的系统时多一个底层数据组织的利器。2. 十字链表的“骨架”顶点与边的精确定义要理解十字链表我们必须先拆解它的两个基本构件顶点节点和边节点。这与邻接表有相似之处但链接关系更为复杂和对称。2.1 顶点节点信息中枢与链表头顶点节点是整个结构的入口和枢纽。它至少需要包含两部分信息数据域存储顶点的实际信息比如用户的ID、城市的名称、任务的编号等。指针域这里就是十字链表与邻接表分道扬镳的关键。一个顶点节点需要维护两个链表的头指针。firstIn指向以该顶点为终点弧头的第一条边即第一条入边所在的边节点。通过这个指针我们可以快速找到所有“指向我”的边。firstOut指向以该顶点为起点弧尾的第一条边即第一条出边所在的边节点。这个指针的功能和邻接表的头指针一致用于快速找到所有“我指向”的边。所有顶点节点通常存储在一个顺序数组顶点表中这样我们可以通过顶点下标O(1)地访问任何一个顶点并拿到它的firstIn和firstOut指针。2.2 边节点十字交错的核心载体边节点是十字链表最精妙的部分它像一张网中的连接点同时属于两个链表。一个边节点通常包含以下五个域以有向边tailVex, headVex为例即从顶点tailVex指向顶点headVextailVex 边的起点弧尾顶点在顶点表中的下标。headVex 边的终点弧头顶点在顶点表中的下标。weight 边的权值如果是带权图。hLink横向链接指针。它指向与当前边拥有相同弧头headVex相同的下一条边。所有弧头相同的边通过hLink串成一个链表这个链表的头就是顶点表中headVex那个顶点的firstIn。因此hLink串起来的是入边链表。tLink纵向链接指针。它指向与当前边拥有相同弧尾tailVex相同的下一条边。所有弧尾相同的边通过tLink串成一个链表这个链表的头就是顶点表中tailVex那个顶点的firstOut。因此tLink串起来的是出边链表。这里有一个非常关键的理解一个边节点同时存在于两个链表中。它既在起点的出边链表里通过tLink连接也在终点的入边链表里通过hLink连接。这就像一个人既在“我关注的人”列表里也在“关注我的人”列表里但物理上只存在一个“人”的实体。为了更直观我们构造一个简单的有向图包含4个顶点V0, V1, V2, V3和有向边V0, V1,V0, V2,V1, V2,V2, V0,V2, V3。其十字链表存储结构如下图所示为简化省略权值顶点表: 下标 | 数据 | firstIn | firstOut --------------------------------- 0 | V0 | [2] | [0] 1 | V1 | [0] | [2] 2 | V2 | [1],[3]| [4] 3 | V3 | [4] | null 边节点池 ([]内为边节点编号): [0]: tail0, head1, hLinknull, tLink[1] [1]: tail0, head2, hLink[3], tLinknull [2]: tail1, head2, hLink[3], tLinknull [3]: tail2, head0, hLinknull, tLink[4] [4]: tail2, head3, hLinknull, tLinknull 链表关系解读 - V0的出边链表(firstOut-[0]): [0] --tLink-- [1] - null。即V0指向V1和V2。 - V0的入边链表(firstIn-[3]): [3] - null。即只有V2指向V0。 - V2的入边链表(firstIn-[1]): [1] --hLink-- [2] - null。即V0和V1都指向V2。 - V2的出边链表(firstOut-[4]): [4] --tLink-- [3] - null? 等等这里需要检查。 实际上[4]的tLink是null[3]的tLink是[4]。所以V2的出边链表是firstOut-[4]? 不对。 根据定义firstOut应指向以V2为tail的第一条边。我们看边节点tail2的有[3]和[4]。 我们需要约定插入顺序。假设按边列表顺序插入 插入2,0为[3]此时V2.firstOut[3]。 插入2,3为[4]将[4]的tLink指向V2当前firstOut即[3]然后更新V2.firstOut[4]。 因此V2的出边链表是firstOut-[4] --tLink-- [3] - null。即V2指向V3和V0。从这个例子可以看到查询V2的所有入边只需从V2.firstIn([1])开始沿hLink遍历即可获得[1]和[2]对应边0,2和1,2非常高效。3. 十字链表的构建、遍历与核心操作剖析理解了静态结构我们来看看如何动态地构建和维护一个十字链表以及如何利用它进行高效的查询。3.1 图的建立插入边的艺术假设我们已经有了顶点数组构建十字链表的过程就是依次插入每条有向边的过程。插入一条新边u, v权值为w的算法步骤如下它清晰地展示了两个链表是如何被同时维护的创建边节点在边节点池可以是一个动态数组或内存池中申请一个新节点e。设置e.tailVex u,e.headVex v,e.weight w。链接到出边链表纵向tLink将e.tLink指向顶点u当前firstOut指针所指向的边节点即e.tLink vertex[u].firstOut。然后更新顶点u的firstOut指针指向新节点e即vertex[u].firstOut e。为什么是头插法头插法实现简单时间复杂度为O(1)。如果采用尾插法则需要遍历找到链表尾部需要O(出度)的时间。对于建图这个通常一次性或批量完成的操作头插法是更常见的选择。链接到入边链表横向hLink将e.hLink指向顶点v当前firstIn指针所指向的边节点即e.hLink vertex[v].firstIn。然后更新顶点v的firstIn指针指向新节点e即vertex[v].firstIn e。这个过程就像把一根新线边节点同时穿入两个不同的线团出边链表和入边链表。头插法的结果是每个链表中的边节点顺序与插入顺序相反。但这通常不影响查询功能。实操心得在实现时特别是用C/C这类语言要特别注意对空指针的处理。在第二步和第三步中如果vertex[u].firstOut或vertex[v].firstIn原本就是NULL那么e.tLink或e.hLink自然就被设置为NULL这正好表示它是链表的最后一个节点。代码逻辑是统一的不需要特殊分支判断。3.2 核心查询操作展现双向高效性十字链表的优势在查询时体现得淋漓尽致。查找顶点u的所有出边EdgeNode *p vertex[u].firstOut; while (p ! NULL) { // 处理边 u - p-headVex权值为 p-weight printf(- %d (weight: %d)\n, p-headVex, p-weight); p p-tLink; // 沿着纵向链表走 }这和邻接表的遍历完全一样时间复杂度为O(出度(u))。查找顶点v的所有入边EdgeNode *p vertex[v].firstIn; while (p ! NULL) { // 处理边 p-tailVex - v权值为 p-weight printf(- %d (weight: %d)\n, p-tailVex, p-weight); p p-hLink; // 沿着横向链表走 }这是十字链表独有的高效操作时间复杂度为O(入度(v))。而在邻接表中这需要O(VE)。判断是否存在边u, v 这需要遍历u的出边链表或v的入边链表。最坏情况是O(max(出度(u), 入度(v)))。虽然比邻接矩阵的O(1)差但对于稀疏图这通常是可以接受的。如果判断操作极其频繁且图较密可能需要结合其他数据结构如哈希表来优化。3.3 图的遍历深度优先与广度优先基于十字链表的图遍历DFS/BFS算法与基于邻接表的版本在逻辑上几乎完全一致只需要将“访问邻接点”的操作从遍历邻接表换成遍历某个顶点的出边链表即可。因为遍历通常是从一个顶点“向外”探索。例如DFS的递归核心部分void DFS(OLGraph G, int v) { visited[v] true; // 遍历v的所有出边即v能到达的顶点 for (EdgeNode *p G.vertex[v].firstOut; p ! NULL; p p-tLink) { int w p-headVex; // w是v的邻接点 if (!visited[w]) { DFS(G, w); } } }BFS同理将队列中顶点的出边链表中的未访问节点入队。注意事项如果你实现的算法需要同时考虑入边和出边例如某些强连通分量算法那么十字链表firstIn的便利性就体现出来了你可以轻松获取一个顶点的“前驱”集合而无需遍历整个图。4. 十字链表的性能权衡与工程实践思考没有一种数据结构是完美的十字链表是在特定需求下对空间和时间做出的精妙权衡。4.1 复杂度分析空间换时间空间复杂度存储V个顶点节点和E个边节点。顶点节点包含数据和两个指针。边节点包含两个顶点下标、权值可选和两个指针。粗略估算为O(V E)。与邻接表相比边节点多了一个指针hLink因此空间开销比邻接表大约多出O(E)。这是为了获得高效入边查询而付出的代价。时间复杂度建图插入一条边是O(1)建图整体为O(E)。查出入边查询顶点v的所有出边为O(出度(v))查询所有入边为O(入度(v))。这是其核心优势。增删边插入边如前所述是O(1)。删除一条指定的边则相对麻烦因为需要在其所在的出边链表和入边链表中都找到它的前驱节点来更新链接最坏需要O(出度(u)入度(v))。如果删除操作频繁需要维护双向链表或额外指针来优化。4.2 对比与选型何时该用十字链表让我们将其与邻接矩阵、邻接表放在一起对比特性邻接矩阵邻接表十字链表空间O(V²)O(VE)O(VE)略高于邻接表查边u,vO(1)O(出度(u))或O(入度(v))需遍历O(出度(u))或O(入度(v))找出边O(V)需扫描一行O(出度(u))O(出度(u))找入边O(V)需扫描一列O(VE)需遍历所有边O(入度(v))增边O(1)O(1)头插O(1)删边O(1)O(出度(u))或O(入度(v)出度(u))O(出度(u)入度(v))适用场景稠密图频繁查边通用尤其稀疏图侧重出边操作有向图且需频繁、高效查询入边选型建议默认选择邻接表对于大多数无向图或者虽然有向但入边查询需求不强烈的场景邻接表简单、空间效率高是首选。十字链表的主场当你的应用严重依赖“查找指向某个顶点的所有边”这一操作时十字链表的优势无可替代。典型场景包括社交网络分析分析用户的粉丝入边列表。任务调度与依赖分析查找哪些任务是当前任务的前置条件入边。编译器技术在程序依赖图、控制流图中分析某个基本块被哪些块跳转而来。知识图谱查询某个实体被哪些关系或实体所指向。邻接矩阵仅适用于顶点数很少或极度稠密边数接近V²且需要频繁进行O(1)复杂度的边存在性判断的场景。4.3 实现细节与避坑指南在实际编码实现十字链表时有几个细节容易出错边节点的唯一性一条有向边在十字链表中只对应一个物理边节点。这个节点通过tLink和hLink被两个链表共享。任何对边节点内容的修改如权值更新都会在两个链表中同时生效这符合逻辑但编程时要心中有数。删除操作的陷阱删除边u, v对应的节点e时必须分别在u的出边链表和v的入边链表中找到e的前驱节点才能正确更新链表链接。如果链表是单向的这个过程需要遍历。一种优化方案是将边节点设计为双向链表节点增加tLinkPrev和hLinkPrev指针这样删除时就能在O(1)时间内找到前驱但空间开销会进一步增加。这再次体现了工程中的权衡。内存管理如果边节点是动态申请的new/malloc在析构图结构时需要妥善释放所有边节点。由于边节点被两个链表共享切忌重复释放。标准的做法是遍历顶点数组对于每个顶点遍历其firstOut链表或firstIn链表依次释放边节点并注意在释放后将该节点的指针置空避免悬空指针。由于一个边节点一定会出现在某个顶点的firstOut链表中所以遍历所有顶点的出边链表足以覆盖所有边节点。序列化与持久化将十字链表存储到文件或数据库会比较复杂因为包含了大量的指针内存地址。通常需要将图数据转化为边列表(u, v, w)这样的三元组序列进行存储加载时再重新构建十字链表结构。我个人在实现一个代码依赖分析工具时就选择了十字链表来存储函数调用图。我需要频繁地分析“这个函数被哪些函数调用”入边查询十字链表让这个核心查询操作变得极其高效虽然增加了约1/3的内存开销但带来的性能提升在百万级函数调用关系的分析中是决定性的。这正印证了那句话在软件工程中没有最好的数据结构只有最适合当前场景的数据结构。十字链表就是为“有向图且重视入边”这一特定场景而生的精致解决方案。