可以看出,这种表示法也非常简单、直接。但是,在关联矩阵的所有
个元素中,只
有
个为非零元。如果网络比较稀疏,这种表示法也会浪费大量的存储空间。但由于
关联矩阵有许多特别重要的理论性质,因此它在网络优化中是非常重要的概念。
例 8 对于例 7 所示的图,如果关联矩阵中每列对应弧的顺序为(1,2),(1,3),(2,4),
(3,2),(4,3),(4,5),(5,3)和(5,4),则关联矩阵表示为
11100000
10110100
01011010
00001101
00000011
同样,对于网络中的权,也可以通过对关联矩阵的扩展来表示。例如,如果网络中
每条弧有一个权,我们可以把关联矩阵增加一行,把每一条弧所对应的权存储在增加的
行中。如果网络中每条弧赋有多个权,我们可以把关联矩阵增加相应的行数,把每一条
弧所对应的权存储在增加的行中。
(iii)弧表示法
弧表表示法将图以弧表(arc list)的形式存储在计算机中。所谓图的弧表,也就是
图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点,共需
个存
储单元,因此当网络比较稀疏时比较方便。此外,对于网络图中每条弧上的权,也要对
应地用额外的存储单元表示。例如,例 7 所示的图,假设弧(1,2),(1,3),(2,4),(3,2),
(4,3),(4,5),(5,3)和(5,4)上的权分别为 8,9,6,4,0,3,6 和 7,则弧表表示如下:
为了便于检索,一般按照起点、终点的字典序顺序存储弧表,如上面的弧表就是按
照这样的顺序存储的。
(iv)邻接表表示法
邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的
邻接表,也就是图的所有节点的邻接表的集合;而对每个节点,它的邻接表就是它的所
有出弧。邻接表表示法就是对图的每个节点,用一个单向链表列出从该节点出发的所有
弧,链表中每个单元对应于一条出弧。为了记录弧上的权,链表中每个单元除列出弧的
另一个端点外,还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数
组表示。例如,例 7 所示的图,邻接表表示为
这是一个 5 维指针数组,每一维(上面表示法中的每一行)对应于一个节点的邻接
表,如第 1 行对应于第 1 个节点的邻接表(即第 1 个节点的所有出弧)。每个指针单元