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

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

个邻接表可以用一个指针数组表示。例如，上例所示的图，邻接表表示为

这是一个 5 维指针数组，每一维（上面表示法中的每一行）对应于一个节点
的邻接表，如第 1 行对应于第 1 个节点的邻接表（即第 1 个节点的所有出弧）。

每个指针单元的第 1 个数据域表示弧的另一个端点（弧的头），后面的数据域表
示对应弧上的权。如第 1 行中的“2”表示弧的另一个端点为 2（即弧为（1，2）），
“8”表示对应弧 (1，2) 上的权为 8；“3”表示弧的另一个端点为 3（即弧为 (1，

3)），“9”表示对应弧（1，3）上的权为 9。又如，第 5 行说明节点 5 出发的弧
有 (5，3)、(5，4)，他们对应的权分别为 6 和 7。

对于有向图 G=(V， A)，一般用 A(i) 表示节点 i 的邻接表，即节点 i 的所有
出弧构的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）。例如上
面例子，A(1) ={2，3}， A(5)={3，4} 等。
4. 星形表示法

星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每
个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一

个单一的数组表示。也就是说，在该数组中首先存放从节点 1 出发的所有弧，然
后接着存放从节点 2 出发的所有孤，依此类推，最后存放从节点 n 出发的所有孤。
对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对
所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。

此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录
每个节点出发的弧的起始地址（即弧的编号）。

在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法
称为前向星形（forward star）表示法。
例如，在例 7 所示的图中，仍然假设弧（1，2），（l，3），（2，4），（3，

195