7.2.3 邻接表在线视频

同学们大家好，我是云南大学信息学院教师孔兵

这节课我们讨论图的另外一种存储结构，邻接表

邻接表是一种链式存储结构

邻接表的存储方式是以指明后继的方式来描述关系

每个表结点描述一个后继，如果有多个后继的话

就把多个表结点组织成一个单链表

下面以有向图G1为例来说明一下如何用邻接表实现图的存储

利用一个一维数组实现顶点的存储

每个数组单元是一个结构体

我们称这个结构体为头结点，头结点中有两个成员

Data用来存储顶点，firstarc是一个指针

指向该顶点后继组成的单链表

后面我们把这个单链表称为该顶点对应的单链表

单链表中，每个后继用一个表结点来描述

表结点中有三个成员

adjvex指明后继的存储位置

info是和弧相关的信息指针

这个指针和数组表示法中ArcCell中的info是一样的

一般图示的时候不画出，nextarc是一个指针

它是用来串联起单链表的

以v4的唯一一个表结点为例

adjvex是0，表示v4有一个后继存在0号单元

这个表结点描述了有序对v4到v1

也就是v4到v1这条弧，info没有画

nextarc为空表示v4没有其它后继了

同学们注意，G1中有4条弧

邻接表中有4个表结点，每个表结点描述一条弧

我们回忆一下前面讨论过的树的存储方法

树的存储方法中有一种是孩子表示法

孩子表示法也是以指孩子

也就是指后继的方式描述关系

所有描述孩子的结点组织成一个单链表

二者实际上上是完全相同的

邻接表同样可以用来存储无向图

在无向图的存储中

采用的办法仍然是一条边作为两条弧来存储

以图G2中的边（v1,v4）例

在顶点v1对应的链表当中

红圈中，第1个表结点的adjvex中是3

指明顶点v1有一个后继存在3号单元

就是顶点v4

描述了v1到v4有一条弧

对称的，v4对应的单链表中

红圈中的表结点，其adjvex为0

指明顶点v4有一个后继存在1号单元

就是顶点v1，描述了v1到v4有一条弧

这两条弧一起，实现了边（v1,v4）的存储

这点在创建无向图存储结构、插入和删除边时要注意

下面结合例子，介绍一下邻接表存储结构的定义

首先，定义最大顶点数为20

看表结点的定义

表结点的三个成员adjvex，nextarc, info刚才我们已经介绍过了

给表结点的结构体起了个类型名叫ArcNode

头结点中有两个成员：data和firstarc

给头结点的结构体取类型名VNode

随后定义了一个数组类型名AdjList

该类型的元素的类型是头结点类型

大小是最大顶点数，这是邻接表中一维数组的类型名

最后是整个图的存储结构，也定义为一个结构体

结构体当中的包含4个成员

一个成员是AdjList类型的一个数组vertices

就是存储顶点的一维数组

另外还有三个成员：两个整型数分别是

图中的顶点个数，边或者弧的个数

最后一个kind，表示图的类型

给这个结构体取名为ALGraph

这就是邻接表存储结构的定义

同学们可以和树的孩子表示法比较一下

结合图邻接表的存储结构

我们简单的讨论一下相关的一些问题

第一，基于有向图的邻接表存储结构求顶点的度

有向图中，求顶点的度需要求出它的出度和入度

二者之和是顶点的度

先考虑求顶点的出度，在邻接表存储的有向图中

求顶点的出度是比较简单的

只需要扫描该顶点对应的单链表

对表结点的个数计数，就可以求出其后继的个数

也就是出度。用指针p扫描对应的单链表

p=G1.vertices[k].firstarc

让p指向单链表中第1个表结点

随后用while循环扫描链表

同时用OD计数链表中结点个数

求入度稍微麻烦一点

邻接表是以指后继的方式描述关系

求入度是要找出一个顶点的所有前驱

这里用两个循环嵌套实现，外层的for循环

它的作用是从0号单元开始扫描整个一维数组

考察图中的每个顶点，当考察位置i的顶点时

用一个while循环扫描该顶点对应的单链表

在扫描单链表的过程中，i的后继adjvex

如果i这个顶点有一个后继是k的话

说明i是k的前驱，入度ID+1

确定了i是前驱后，while语句不需要继续循环了

break跳出while循环，否则需要扫描整个i的单链表

才能确定i不是k的前驱。for循环结束

所有顶点都考察完成后，可以求得k的入度

入度和出度都求完成以后

二者相加就是我们的求的顶点的度

无向图中求顶点的度比较简单

扫描该顶点对应的单链表

对标节点计数就可以了

用邻接表同样可以实现有向网和无向网的存储

边或弧存的时候

表结点中的成员adjvex存权值就可以

数组表示法和邻接表都可以用来实现四类图的存储

二者也各有特点

数组表示法中利用二维数组存储关系

二维数组的大小和顶点数有关

也就是说图中顶点数确定了

其存储空间的需求就确定了

边或弧是多还是少都一样

所以数组表示法适合存储稠密图邻接表是通过表结点描述关系

有多少弧就有多少表结点

所以邻接表

适合存储稀疏图，稀疏图中边或弧比较少

我们基于数组表示法讨论了求第一个邻接点

和求下一个邻接点的函数

课后请同学们思考一下

基于邻接表如何实现这两个函数的函数

前面我们讨论了基于有向图的邻接表存储结构求顶点的度

从讨论中可以看出

在邻接表实现的有向图存储结构当中

找顶点的后继，求出度是比较容易的

而求入度时必须进行二维扫描

考察每个顶点，再扫描该顶点对应的单链表

原因是邻接表以指后继的方式描述关系

导致找后继求出度比较容易

找前驱比较麻烦

顺便说一句，数组表示法中找前驱和后继都比较容易

这算是数组表示法的一个优点

如果在有的问题背景下

我们更多的是需要找前驱

可以考虑建立它的逆邻接表的存储结构

注意无向图没有什么逆邻接表

逆邻接表是对有向图来说的

邻接表，它表结点成员adjvex指明后继

描述关系

逆邻接表呢，刚好相反

它是通过指前驱的来描述关系

仍然以图G1为例

红圈中表结点的0

所表示的是v3有一个前驱存在0号单元

就是顶点v1

这里就用指前驱的方式

描述了v1到v3这条弧

G1的逆邻接表，如图中所示

对称的，在逆邻接表中

求前驱比较方便，求后继麻烦一些

也是需要进行一次二维的扫描

好，同学们

这节课就到这

下次课再见