Page 204 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质，因此
它在网络优化中是非常重要的概念。

例 对于上例所示的图，如果关联矩阵中每列对应弧的顺序为 (1，2)，(1，3)，
(2，4)，(3，2)，(4，3)，(4，5)，(5，3) 和 (5，4)，则关联矩阵表示为

同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果
网络中每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权
存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相

应的行数，把每一条弧所对应的权存储在增加的行中。
3. 弧表表示法
弧表表示法将图以弧表的形式存储在计算机中。所谓图的弧表，也就是图的

弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需 2m 个
存储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，
也要对应地用额外的存储单元表示。例如，例 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，则弧表表示如表 8-1 所示。

为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表

就是按照这样的顺序存储的。
邻接表表示法邻接表表示法将图以邻接表的形式存储在计算机中。所谓图的
邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是

它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节
点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中
每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整

194