IT评测·应用市场-qidao123.com技术社区

标题: 【数据结构】图论存储革新：十字链表双链筹划高效解决有向图入度查询难题 [打印本页]

作者: 诗林 时间: 2025-4-8 12:45
标题: 【数据结构】图论存储革新：十字链表双链筹划高效解决有向图入度查询难题

导读

大家好，很高兴又和大家晤面啦！！！
在图的链式存储探索中，我们曾解析邻接表的灵活性与范围——它虽以链表动态管理边集，却难明有向图入度查询的服从困局。
如何让存储结构在空间与时间上实现双重突破？
本文将聚焦一种革新筹划——十字链表，它通过顶点表双向关联出边与入边，以共享边节点的巧思，实现出入度的高效统管。
从结构界说到代码落地，层层拆解这一“双向链表”如作甚有向图赋予全新生命力！
一、邻接表的优缺点

邻接表作为图的链式存储结构，通过顺序存储的顶点表可以或许快速的访问各个顶点的信息，通过链式存储的边表，可以或许动态的对边集进行增加与删除操作；
相比于邻接矩阵的使用空间换时间，邻接表通过链表存储边的信息，大大低落了空间的斲丧。
顶点表中的每个结点都可以通过边表头指针域来管理边的信息。对于有向图而言，邻接表则是可以或许通过出边表快速获取顶点的出度信息；
但是，在有向图中，除了出度还有入度。当我们需要获取一个顶点x的入度信息时，我们只可以或许斲丧大量的时间遍历整个邻接表，通过判定其他顶点的出边表中是否存在弧头尾为x的结点，以此来获取顶点x的入度信息。
如果说我们可以或许在顶点表中同时管理出度和入度的信息，那么邻接表的这个短板是不是就被解决了呢？
通过顶点表同时管理出度与入度信息的数据结构就是我们本日要先容的十字链表；
二、十字链表

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

在十字链表中，存储顶点信息的顺序表我们同样将其称之为顶点表。与邻接表不同的是，十字链表顶点表不仅可以或许管理结点的出度，还可以或许管理结点的入度。
十字链表中的顶点表的各个顶点结点有3个域：

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

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

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

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

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

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

2.2.1 顶点表

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

出边表就是邻接表：以该顶点为弧尾，别的顶点为弧头的弧对应的边结点所组成的链表
- 如弧 < a , b > <a, b> <a,b>就是顶点a的邻接表中的边结点
- 我们可以通过指向出边表的指针firstout找到以该顶点为弧尾的所有弧；
入边表就是逆邻接表：以别的顶点为弧尾，该顶点为弧头的弧对应的边结点所组成的链表
- 如弧 < a , b > <a, b> <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 > <a, b>, <c, b> <a,b>,<c,b> 这两条弧的弧头雷同，都是以顶点 b b b 为弧头，因此这两条弧对应的边结点在同一个头链表中；
< b , c > , < d , c > <b, c>, <d, c> <b,c>,<d,c> 这两条弧的弧头雷同，都是以顶点 c c c 为弧头，因此这两条弧对应的边结点在同一个头链表中；

同理，尾链域tlink所指向的是由所有弧中弧尾结点雷同的弧对应的边结点所组成的链表；
边结点中的信息域info存储的是该结点对应的弧的信息，比如该弧的权值。
因此如果我们是通过十字链表存储一张有向网，那么我们就需要通过该域记录每条弧的权值；
若我们存储的是平凡的有向图，我们是可以省略info域的。
2.2.3 十字链表

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

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

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

按出边与入边的方式分类：
- < a , b > → 结点 b 的入边 ↓ 结点 a 的出边 <a, b> → 结点b的入边 \\ \hspace{1em}\downarrow \\结点a的出边 <a,b>→结点b的入边↓结点a的出边
按照弧头弧尾的方式进行分类：
- < a , b > → 以结点 b 为弧头 ↓ 以结点 a 为弧尾 <a, b> → 以结点b为弧头\\ \hspace{1em}\downarrow \\以结点a为弧尾 <a,b>→以结点b为弧头↓以结点a为弧尾

可以看到，不管是那种分类方式，对于弧 < a , b > <a, b> <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 时间复杂度

当我们对一个十字链表进行遍历时，实际上就是在遍历顶点表的底子上，分别对每个顶点的邻接表和逆邻接表进行遍历；
对于有向图，所有顶点的入度之和、出度之和与边的总数满意以下关系：
∑ v ∈ V deg ⁡ − ( v ) = ∑ v ∈ V deg ⁡ + ( v ) = ∣ E ∣ \sum_{v \in V} \deg^{-}(v) = \sum_{v \in V} \deg^{+}(v) = |E| v∈V∑deg−(v)=v∈V∑deg+(v)=∣E∣
此中

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

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

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

5.1 上风

在十字链表中，由于我们通过顶点表同时管理了一个结点的出度与入度，因此相比于邻接表，十字链表大大提高了查找顶点入度的服从；
在十字链表中，出边表和入边表共享着所有的边结点，制止了管理出边表与入边表时的双重存储，大大节流了内存空间
由于十字链表在存储边结点时采用的是链表的形式，因此支持动态的弧的插入与删除；
当我们碰到需要同时处理出入与入度的问题时，我们就可以通过十字链表来快速实现；
5.2 劣势

十字链表的存储对象被限定在了有向图，该数据结构能且仅能存储有向图，无法实现无向图的存储；
由于十字链表需要同时管理结点的出度与入度，因此我们在实现的过程中，其代码量会非常的庞大；
5.3 特点

十字链表相当于将邻接表中无法管理入度的不敷以及邻接矩阵中空间斲丧过大的不敷同时完善了，因此十字链表非常适合进行有向希奇图的存储；
十字链表与邻接表一样，由于对有向边采用的是链表进行的存储，因此一张图所对应的十字链表并不是唯一的，但是一个十字链表表示的肯定是一张确定的有向图；
结语

十字链表以顶点表为枢纽，通过出边与入边链表的交叉绑定，攻克了邻接表处理有向图入度的服从短板。其“一节点双归属”的筹划，既保留了链表的动态扩展性，又制止了邻接矩阵的空间冗余，成为希奇有向图的优选方案。
无向图中一条边需被两个顶点共享，如何制止重复存储？下一篇将揭秘邻接多重表的精妙筹划，看它如何以“边节点共享”破局！

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)