十字链表与邻接多重表的画法

前言

近期一直在构建算法技能树的数据&＃xff0c;借此机会&＃xff0c;重新把数据结构与算法又温习了一遍&＃xff0c;在看到十字链表与邻接多重表的画法时&＃xff0c;十分的不理解&＃xff0c;在C站找资料时&＃xff0c;发现也看不懂&＃xff0c;于是上B站&＃xff0c;终于明白了十字链表与多重邻接表的画法。

一、十字链表

我们以下面的有向图为例来进行讲解

首先我们有几个定义要搞清楚&＃xff1a;

如果&＃xff1a;

则我们称V0是弧尾&＃xff0c; v3是弧头

反之&＃xff0c;如果&＃xff1a;

则我们称v1是弧尾&＃xff0c;v0是弧头。

firstin&＃xff1a; 入边表头指针&＃xff0c;指向该顶点的入边表中第一个节点
firstout&＃xff1a; 出边表头指针&＃xff0c;指向该顶点的出边表中第一个节点

tailvex&＃xff1a; 弧的尾节点
headvex&＃xff1a; 弧的头节点

headlink&＃xff1a; 指向和这条弧有相同头节点的点&＃xff1b;同头
taillink&＃xff1a; 指向和这条弧有相同尾节点的点&＃xff1b; 同尾

用下面的图表示&＃xff1a;

以上重要概念都清楚后&＃xff0c;下面我们开始画十字链表。

总的来说&＃xff0c;分为三步&＃xff1a;

1.画邻接表

接着&＃xff0c;进入第二步

2.增加弧节点的域

我们将上图换成十字链表的格式

我们将其补齐&＃xff0c;如下图&＃xff1a;

然后&＃xff0c;我们把这四个顶点标到图上去&＃xff0c;如下&＃xff1a;

接着&＃xff0c;进入第三步

3.自己指向自己

第二步完成后&＃xff0c;我们的图变成了现在这个样子&＃xff1a;

接下来&＃xff0c;我们就开始自己指自己的过程
从v0开始&＃xff0c;将图中v0相连

接着v1&＃xff0c;将图中所有v1相连

接着v2,v3&＃xff0c;最终的结果如下&＃xff1a;

至此&＃xff0c;上图就是例子中有向图的十字链表。

二、邻接多重表

我们以下面的无向图为例

ivex、jvex&＃xff1a; 与某条边依附的两个顶点在顶点表中的下标

ilink&＃xff1a; 指向依附顶点ivex的下一条边
jlink&＃xff1a; 指向依附顶点jvex的下一条边

1.画顶点

上面的无向图告诉我们它有四个顶点和五条边&＃xff0c;所以&＃xff0c;我们我们先将四个顶点和五条边的边表结构画出来&＃xff0c;由于是无向图&＃xff0c;所以ivex和jvex的顺序是可以互换的。

2.画边

3.自己指向自己

首先&＃xff0c;我们从v0开始&＃xff0c;v0的下标是0&＃xff0c;将所有与v0有关的边连接起来。
其中&＃xff0c;最后一个矩形&＃xff0c;0和2之间的^表示空&＃xff0c;因为再往下找没有与v0有关的边了&＃xff0c;所以填入空

再连接所有与v1有关的边

接着是v2,v3

至此&＃xff0c;上图就是例子中无向图的邻接多重表

最后&＃xff0c;看完这篇文章还没懂的话可以点击一下链接观看视频&＃xff1a;

1.十字链表画法
2.邻接多重表