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

第八章 图与网络模型及方法应用

使用邻接矩阵表示将导致大量存储资源的浪费，并可能延长查询特定连接所需的
时间。

图 8-2 有向图

例 7 对于图 2 所示的有向图，可以用邻接矩阵表示为

同样，对于网络中的权，也可以用类似邻接矩阵的 n×n 矩阵表示。只是此
时一条弧所对应的元素不再是 1，而是相应的权而已。如果网络中每条弧赋有多

种权，则可以用多个矩阵表示这些权。
2. 关联矩阵表示法
关联矩阵表示法是将图以关联矩阵的形式存储在计算机中．图 G =(V， A)

的关联矩阵 B 是如下定义的： B 是一个 n×m 的矩阵，即

也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。
如果一个节点是一条弧的起点，则关联矩阵中对应的元素为 1；如果一个节点是
一条弧的终点，则关联矩阵中对应的元素为 1；如果一个节点与一条弧不关联，

则关联矩阵中对应的元素为 0。对于简单图，关联矩阵每列只含有两个非零元（一
个＋ 1，一个－ 1）。可以看出，这种表示法也非常简单、直接。但是，在关联
矩阵的所有 nm 个元素中，只有 2m 个为非零元。如果网络比较稀疏，这种表示

193