【数据结构】图论存储革新：十字链表双链设计高效解决有向图入度查询难题

导读

大家好，很高兴又和大家见面啦！！！

在图的链式存储探索中，我们曾解析邻接表的灵活性与局限——它虽以链表动态管理边集，却难解有向图入度查询的效率困局。

如何让存储结构在空间与时间上实现双重突破？

本文将聚焦一种革新设计——十字链表，它通过顶点表双向关联出边与入边，以共享边节点的巧思，实现出入度的高效统管。

从结构定义到代码落地，层层拆解这一“双向链表”如何为有向图赋予全新生命力！

一、邻接表的优缺点

邻接表作为图的链式存储结构，通过顺序存储的顶点表能够快速的访问各个顶点的信息，通过链式存储的边表，能够动态的对边集进行增加与删除操作；

相比于邻接矩阵的利用空间换时间，邻接表通过链表存储边的信息，大大降低了空间的消耗。

顶点表中的每个结点都可以通过边表头指针域来管理边的信息。对于有向图而言，邻接表则是能够通过出边表快速获取顶点的出度信息；

但是，在有向图中，除了出度还有入度。当我们需要获取一个顶点x的入度信息时，我们只能够消耗大量的时间遍历整个邻接表，通过判断其他顶点的出边表中是否存在弧头尾为x的结点，以此来获取顶点x的入度信息。

如果说我们能够在顶点表中同时管理出度和入度的信息，那么邻接表的这个短板是不是就被解决了呢？

通过顶点表同时管理出度与入度信息的数据结构就是我们今天要介绍的十字链表；

二、十字链表

十字链表（Orthogonal List）是有向图的一种链式存储结构，它的是实现与邻接表一样，通过顺序表存储顶点信息，通过链表存储弧的信息。

2.1 结点结构

在十字链表中，存储顶点信息的顺序表我们同样将其称之为顶点表。与邻接表不同的是，十字链表顶点表不仅能够管理结点的出度，还能够管理结点的入度。

十字链表中的顶点表的各个顶点结点有3个域：

• data域：用于存放顶点数据信息
• firstin域：指向以该顶点为弧头的第一条弧（入度）
• firstout域：指向以该顶点为弧尾的第一条弧（出度）

在十字链表中，管理边的链表有两个：

• 出边链表（邻接表）：用于存放顶点的出边信息
• 入边链表（逆邻接表）：用于存放顶点的入度信息

链表中的每一个结点都由五部分组成：

• tailvex域：存放弧尾的顶点编号
• headvex域：存放弧头的顶点编号
• hlink域：存放弧头相同的下一条弧
• tlink域：存放弧尾相同的下一条弧
• info域：存放该弧的相关信息

十字链表的图看上去似乎密密麻麻的箭头，无法正确的辨别到底谁是谁。接下来我们就来理解以下十字链表的原理；

2.2 原理解释

2.2.1 顶点表

十字链表通过顶点表存储顶点信息并且管理出边表和入边表。

• 出边表就是邻接表：以该顶点为弧尾，其它顶点为弧头的弧对应的边结点所组成的链表
  • 如弧 $<a,b>$就是顶点a的邻接表中的边结点
  • 我们可以通过指向出边表的指针firstout找到以该顶点为弧尾的所有弧；
• 入边表就是逆邻接表：以其它顶点为弧尾，该顶点为弧头的弧对应的边结点所组成的链表
  • 如弧 $<a,b>$ 就是顶点b的逆邻接表中的边结点
  • 我们可以通过指向入边表的指针firstin找到以该顶点为弧头的所有弧；

2.2.2 边结点

在十字链表中，出边表和入边表中的结点是共用的，也就是说同一个结点会同时存在于两个边表中，因此我们这里主要分析边结点的作用；

在边结点中，通过弧尾顶点域和弧头顶点与存储对应顶点的编号信息：

• tailvex: 记录弧尾的编号信息；
• headvex: 记录弧头的编号信息；

通过记录的编号信息，我们就可以在顶点表中找到该顶点的信息，这样我们就能够确定当前边结点所对应的弧；

边结点中的头链域hlink所指向的是由所有弧中弧头结点相同的弧对应的边结点所组成的链表；

这里比较绕，我们通过图示来理解：

在上示的有向图中，有4条弧 E = { < a , b > , < b , c > , < c , b > , < d , c > } E = \{<a, b>, <b, c>, <c, b>, <d, c>\} E={<a,b>,<b,c>,<c,b>,<d,c>}，如果我们将弧头相同的弧放入一个链表中，那么我们就可以得到两个头链表：

• $<a,b>,<c,b>$ 这两条弧的弧头相同，都是以顶点 $b$ 为弧头，因此这两条弧对应的边结点在同一个头链表中；
• $<b,c>,<d,c>$ 这两条弧的弧头相同，都是以顶点 $c$ 为弧头，因此这两条弧对应的边结点在同一个头链表中；

同理，尾链域tlink所指向的是由所有弧中弧尾结点相同的弧对应的边结点所组成的链表；

边结点中的信息域info存储的是该结点对应的弧的信息，比如该弧的权值。

因此如果我们是通过十字链表存储一张有向网，那么我们就需要通过该域记录每条弧的权值；

若我们存储的是普通的有向图，我们是可以省略info域的。

2.2.3 十字链表

十字链表是由顶点表和所有的边结点相互关联所形成的一张交叉链表：

• 顶点表中将各顶点分为两个链表：
  • 出边表：由该顶点为弧尾的边结点组成的链表
  • 入边表：由该顶点为弧头的边结点组成的链表
• 边结点又通过头链域和尾链域自动分成了两个链表：
  • 头链表：由弧头编号相同的顶点所组成的链表
  • 尾链表：由弧尾编号相同的顶点所组成的链表

十字链表中的所有边结点不管是按照出入边的方式进行分类还是按照弧头弧尾的方式进行分类，同一个结点一定会同时归属于两个链表中，这里我们以弧 $<a,b>$ 为例：

• 按出边与入边的方式分类：
  • $$\begin{gathered} <a,b>\to 结点b的入边 \\ \downarrow \\ 结点a的出边 \end{gathered}$$
• 按照弧头弧尾的方式进行分类：
  • $$\begin{gathered} <a,b>\to 以结点b为弧头 \\ \downarrow \\ 以结点a为弧尾 \end{gathered}$$

可以看到，不管是那种分类方式，对于弧 $<a,b>$ 而言，它都是同时存在于两个链表中，并且这两个链表我们可以认为其在逻辑上十字相交。

右上角的出边表与入边表组成的链表矩阵中，我们可以看到每一个结点所处的位置正好是对应两个链表的十字交点，因此这种存储结构称为十字链表。

三、存储结构

十字链表的存储结构与邻接表一样，都是需要定义两种结点类型；

与邻接表不同的是两种结点的结构上有所区别：

#define MAXSIZE 5
typedef char VexType;
typedef int ArcType;
//边结点
typedef struct ArcNode {int tailvex;				// 弧尾顶点编号int headvex;				// 弧头顶点编号struct ArcNode* hlink;		// 头链表指针struct ArcNode* tlink;		// 尾链表指针ArcType info;				// 边信息（权值），可以省略
}ArcNode;
//顶点结点
typedef struct VexNode {VexType data;				// 顶点信息ArcNode* firstin;			// 入边表（逆邻接表）ArcNode* firstout;			// 出边表（邻接表）
}VexNode;
//十字链表
typedef struct Orthogonal_List {VexNode vex_list[MAXSIZE];	// 顶点表int vex_num;				// 当前顶点数两int arc_num;				// 当前弧的数量
}OLGraph;

整个结构的定义并不困哪，我们只需要在邻接表的基础上稍作修改即可，这里就不再展开；

这里需要注意，如果当前的有向图就是一张普通的有向图，那么我们就可以在边结点中省去信息域info；

在顶点表中，我们也可以通过增加两个变量分别记录该顶点的出度与入度，这个就看个人习惯了。

四、算法评价

对十字链表的算法评价我们同样以十字链表的遍历进行评价；

4.1 时间复杂度

当我们对一个十字链表进行遍历时，实际上就是在遍历顶点表的基础上，分别对每个顶点的邻接表和逆邻接表进行遍历；

对于有向图，所有顶点的入度之和、出度之和与边的总数满足以下关系：

$$\sum _{v\in V}{\mathrm{deg}}^{-}(v)=\sum _{v\in V}{\mathrm{deg}}^{+}(v)=|E|$$

其中

• ${\mathrm{deg}}^{-}(v)$：顶点 $v$ 的入度（指向 $v$ 的边数）。
• ${\mathrm{deg}}^{+}(v)$：顶点 $v$ 的出度（从 $v$ 出发的边数）。
• $|E|$：图的边的总数。

因此当我们要遍历整个有向图时，我们只需要遍历顶点以及所有顶点的入度或者所有顶点的出度即可，对应的时间复杂度为：$T(N)=O(|V|+|E|)$

4.2 空间复杂度

在十字链表中，我们只需要给每个顶点申请一个结点空间，给每条弧申请一个结点空间即可，因此其所对应的空间复杂度应该是： $T(N)=O(|V|+|E|)$

五、优势与劣势

5.1 优势

在十字链表中，因为我们通过顶点表同时管理了一个结点的出度与入度，因此相比于邻接表，十字链表大大提高了查找顶点入度的效率；

在十字链表中，出边表和入边表共享着所有的边结点，避免了管理出边表与入边表时的双重存储，大大节省了内存空间

由于十字链表在存储边结点时采用的是链表的形式，因此支持动态的弧的插入与删除；

当我们遇到需要同时处理出入与入度的问题时，我们就可以通过十字链表来快速实现；

5.2 劣势

十字链表的存储对象被限制在了有向图，该数据结构能且仅能存储有向图，无法实现无向图的存储；

由于十字链表需要同时管理结点的出度与入度，因此我们在实现的过程中，其代码量会十分的庞大；

5.3 特点

十字链表相当于将邻接表中无法管理入度的不足以及邻接矩阵中空间消耗过大的不足同时完善了，因此十字链表十分适合进行有向稀疏图的存储；

十字链表与邻接表一样，因为对有向边采用的是链表进行的存储，因此一张图所对应的十字链表并不是唯一的，但是一个十字链表表示的一定是一张确定的有向图；

结语

十字链表以顶点表为枢纽，通过出边与入边链表的交叉绑定，攻克了邻接表处理有向图入度的效率短板。其“一节点双归属”的设计，既保留了链表的动态扩展性，又避免了邻接矩阵的空间冗余，成为稀疏有向图的优选方案。

无向图中一条边需被两个顶点共享，如何避免重复存储？下一篇将揭秘邻接多重表的精妙设计，看它如何以“边节点共享”破局！

🔍 本文是否让你对链式存储的迭代有了新认知？点赞❤️支持原创深度解析！
📁 收藏随时回溯技术细节，转发🔗与团队探讨方案优化。
💬 评论区畅聊你的存储设计心得，或抛出疑惑共同探讨！
🔔 关注不迷路，下篇《邻接多重表：无向图存储的优雅解法》即将上线！

🚀 你的每一次互动，都是技术深水区探索的助力！