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

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

2），（4，3），（4，5），（5，3）和（5，4）上的权分别为 8，9，6，4，0，
3，6 和 7。此时该网络图可以用前向星形表示法表示为表 8-2 和表 8-3 。

在数组 point 中，其元素个数比图的节点数多 1（即 n ＋ 1），且一定有
point(1)= 1，point(n ＋ 1)= m ＋ 1。对于节点 i ，其对应的出弧存放在弧信息数组
的位置区间为 [point(i)， point(i ＋ 1) － 1]，如果 point(i)=point(i ＋ 1) ，则节点 i

没有出弧。这种表示法与弧表表示法也非常相似，“记录弧信息的数组”实际上
相当于有序存放的“弧表”。只是在前向星形表示法中，弧被编号后有序存放，

并增加一个数组记录每个节点出发的弧的起始编号。
前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个
节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形表
示法：首先存放进入节点 1 的所有孤，然后接着存放进入节点 2 的所有弧，依此

类推，最后存放进入节点 n 的所有孤。对每条弧，仍然依次存放其起点、终点、
权的数值等有关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一
般还用一个数组记录每个节点的入孤的起始地址（即弧的编号）。例如，上例所

示的图，可以用反向星形表示法表示为表 8-4 和表 8-5。

如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有
入弧，则可以综合采用前向和反向星形表示法。当然，将孤信息存放两次是没有

196