7.2.2 数组表示法（2）在线视频

同学们，大家好

我是云南大学信息学院教师孔兵

这节课我们继续讨论和数组表示法相关的一些问题

前面我们讨论了图的数组表示法

基于数组表示法实现图的基本操作是需要关注的问题

首先讨论求顶点的度

顶点度的概念讨论过，有向图中

一个顶点的度分为出度和入度

二者之和就是该顶点的度

无向图中，一个顶点的度是和它相关的边的数目

我们以G1为例，讨论基于数组表示法如何求有向图顶点的度

设求顶点v1的度，存储结构如图所示

初始化出度OD，入度ID为0，TD是度

确定v1在一维数组中的存储位置

赋值给k，这里v1的位置是0

首先求顶点的出度，就有向图来说

一个顶点的出度是以它为尾的弧的数目

也就是后继的个数

通过循环，扫描该顶点对应的行

对adj为1的元素进行计数，就是其后继的个数

如求v1的出度，如图所示，扫描arcs的第0行

有2个1，那么v1的出度为2

求顶点的入度，有向图中

一个顶点的入度是以它为头的弧的数目

也就是前驱的个数

通过循环，扫描该顶点对应的列

对adj为1的元素进行计数

就是其前驱的个数。如求v1的入度

如图所示，扫描arcs的第0列

有1个1，那么v1的入度为1

v1的度是出度和入度之和，所以v1的度为3

无向图中求顶点的度更简单一些

因为一条边被作为2条弧存储

扫描该顶点对应的行或者列，计数就可以了

下一个和存储相关的问题，是找一个顶点邻接点的问题

在图的定义和术语那一节，介绍了邻接点的概念

我们提到过一个问题，有多个邻接点的时候

谁是第一个邻接点?从逻辑结构来看

实际是无法确定的。只有实现了它的存储

确定了找邻接点的方法

才能说谁是第1个，谁是第2个

以无向图G2为例

看一下求第一个邻接点和下一个邻接点的方法

首先，求第1个邻接点

求第1个邻接点的函数是FirstAdjVex

它的返回值是个整型数，如果成功的找到第1个邻接点

返回第1个邻接点在一维数组中的位置

如果失败，就是该顶点一个邻接点都没有

返回一个-1。涉及到的参数有两个

一个要找邻接点的图，我们要操作的对象

这里是用数组表示法存储的图G

另外一个整型数v表示要找邻接点的顶点

直接用该顶点的存储位置表示

参数的含义就是在图G中，找顶点v的第一个邻接点

大家要注意，后面的算法中

涉及到顶点的一般都是直接给出它的存储的位置

不是给出顶点本身

假设G2中，求顶点v=2的第一个邻接点

也就是求v3的第一个邻接点

方法是扫描二维数组的第二行

遇到第一个1所对应的列号

就是v3的第一个邻接点的存储位置

例子中是第2行第1列的1

说明v3的第一个邻接点是存储在1号位置的v2

程序中，用一个for循环来实现对第v行的扫描

如果arcs中第v行第i列的adj是1

则返回i，这就是找到的第一个邻接点

如果循环结束以后仍然没有返回

那么说明没有邻接点，返回-1

求下一个邻接点的函数是NextAdjVex

返回值是整型，其含义和和求第一个邻接点的函数相同

成功，返回下一个邻接点的存储位置

失败，返回-1。涉及的参数有三个

一个是作为操作对象的图G

一个是我们要求邻接点的顶点v

注意最后一个w，这个w是已经求得的v的一个邻接点

求下一个邻接点函数求的是v的w之后的下一个邻接点

仍然以G2为例

设已经求得了存储在2号单元顶点v3的第一个邻接点

是存储在1号单元的顶点v2

调用求下一个邻接点函数

求2的1之后的下一个邻接点

这时参数v=2，w=1，方法和求第一个邻接点类似

也是扫描二维数组中的第2行

从w+1列开始扫描，遇到的第1个1所对应的列号

就是下一个邻接点，从图上可以看出

是第2行第3列

也就是v3的下一个邻接点是存储在3号单元的顶点v4

数组表示法可以用来存储带权的图

也就是网。我们以有向网为例

如右图所示

实现它的存储结构仍然是用二个数组

一维数组当中仍然是存储顶点

和有向图、无向图中是一样的

二维数组有些不同，网中除了表示关系有无外

还需要表示权值

所以ArcCell的adj这个成员不能仅存储0或者1

这里，我们是这样来约定的

如果这条弧是存在的，adj中存这条弧的权值

如果这条弧是没有的，那么adj就存一个无穷infinity

这个无穷在存储结构定义是被定义为系统的最大整数

在求最短路径等算法实现时，要注意溢出问题

同学们课后可以通过实现图的存储结构

进一步熟悉数组表示法

好同学们，数组表示法我们就讨论到这

下次课再见