权为8:“3”表示弧的另一个端点为3(即弧为(1,3),“9”表示对应弧(1,3)上的权 为9。又如,第5行说明节点5出发的弧有(5,3)、(5,4),他们对应的权分别为6和7 对于有向图G=(,A),一般用A()表示节点i的邻接表,即节点的所有出弧构 成的集合或链表(实际上只需要列出弧的另一个端点,即弧的头)。例如上面例子, A(1)={2,3},A(5)={34}等。这种记法我们在本书后面将会经常用到 (v)星形表示法 星形(sar)表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点 它也是记录从该节点出发的所有弧,但它不是采用单向链表而是采用一个单一的数组表 示。也就是说,在该数组中首先存放从节点1出发的所有弧,然后接着存放从节点2 出发的所有孤,依此类推,最后存放从节点n出发的所有孤。对每条弧,要依次存放其 起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号 只是从同一节点出发的弧的顺序可以任意排列。此外,为了能够快速检索从每个节点出 发的所有弧,我们一般还用一个数组记录每个节点出发的弧的起始地址(即弧的编号)。 在这种表示法中,可以快速检索从每个节点出发的所有弧,这种星形表示法称为前向星 形( forward star)表示法。 例如,在例7所示的图中,仍然假设弧(1,2),(1,3),(2,4),(3,2),(4,3),(4,5) (5,3)和(54)上的权分别为8,9,6,4,0,3,6和7。此时该网络图可以用前向 星形表示法表示如下 节点对应的出弧的起始地址编号数组(记为 起始地址poin(i) 记录弧信息的数组 弧编号1 2 7 终点 4324 5430 在数组 point中,其元素个数比图的节点数多1(即n+1),且一定有pomn(1)=1 poin(n+1)=m+1。对于节点i,其对应的出弧存放在弧信息数组的位置区间为 Ipoint(i), point(i+1)-1 如果poin(1)= point(i+1),则节点i没有出弧。这种表示法与弧表表示法也非常相 似,“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中 弧被编号后有序存放,并增加一个数组(poin)记录每个节点出发的弧的起始编号。 前向星形表示法有利于快速检索每个节点的所有出弧,但不能快速检索每个节点的 所有入弧。为了能够快速检索每个节点的所有入孤,可以采用反向星形( reverse star) 表示法:首先存放进入节点1的所有孤,然后接着存放进入节点2的所有弧,依此类推 最后存放进入节点n的所有孤。对每条弧,仍然依次存放其起点、终点、权的数值等有 关信息。同样,为了能够快速检索从每个节点的所有入弧,我们一般还用一个数组记录 每个节点的入孤的起始地址(即弧的编号)。例如,例7所示的图,可以用反向星形表 示法表示为如下形式: 节点对应的入弧的起始地址编号数组(记为 point) 节点号11234_56
-49- 权为 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} 等。这种记法我们在本书后面将会经常用到。 （v）星形表示法 星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点， 它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表 示。也就是说，在该数组中首先存放从节点 1 出发的所有弧，然后接着存放从节点 2 出发的所有孤，依此类推，最后存放从节点 n 出发的所有孤。对每条弧，要依次存放其 起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号， 只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出 发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。 在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星 形（forward star）表示法。 例如，在例 7 所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5）， （5,3）和（5,4）上的权分别为 8，9，6，4，0，3，6 和 7。此时该网络图可以用前向 星形表示法表示如下： 节点对应的出弧的起始地址编号数组（记为 point ） 节点号 i 1 2 3 4 5 6 起始地址 point(i) 1 3 4 6 7 9 记录弧信息的数组 弧编号 1 2 3 4 5 6 7 8 起点 1 1 2 3 4 4 5 5 终点 2 3 4 2 3 5 3 4 权 8 9 6 4 0 3 6 7 在数组 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 没有出弧。这种表示法与弧表表示法也非常相 似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中， 弧被编号后有序存放，并增加一个数组（ point ）记录每个节点出发的弧的起始编号。 前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的 所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star） 表示法：首先存放进入节点 1 的所有孤，然后接着存放进入节点 2 的所有弧，依此类推， 最后存放进入节点 n 的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有 关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一般还用一个数组记录 每个节点的入孤的起始地址（即弧的编号）。例如，例 7 所示的图，可以用反向星形表 示法表示为如下形式： 节点对应的入弧的起始地址编号数组（记为 rpoint ） 节点号 i 1 2 3 4 5 6
匚起始地址mom(_113689 记录弧信息的数组 弧编号 234 4340 645 742 854 如果既希望快速检索每个节点的所有出弧,也希望快速检索每个节点的所有入弧, 则可以综合采用前向和反向星形表示法。当然,将孤信息存放两次是没有必要的,可以 只用一个数组( trace)记录一条弧在两种表示法中的对应关系即可。例如,可以在采用 前向星形表示法的基础上,加上上面介绍的 point数组和如下的 trace数组即可。这相 当于一种紧凑的双向星形表示法如下所示: 两种表示法中的弧的对应关系(记为race) 反向法中弧编号 正向法中弧编号 trace(j) 对于网络图的表示法,我们作如下说明: ①星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的 优点是占用的存储空间较少,并且对那些不提供指针类型的语言(如 FORTRAN语言 等)也容易实现。邻接表表示法对那些提供指针类型的语言(如C语言等)是方便的, 且增加或删除一条弧所需的计算工作量很少,而这一操作在星形表示法中所需的计算工 作量较大(需要花费O(m)的计算时间)。有关“计算时间”的观念是网络优化中需要 考虑的一个关键因素 ②当网络不是简单图,而是具有平行弧(即多重弧)时,显然此时邻接矩阵表示 法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。 ③上述方法可以很方便地推广到可以处理无向图的情形,但由于无向图中边没有 方向,因此可能需要做一些自然的修改。例如,可以在计算机中只存储邻接矩阵的一半 信息(如上三角部分),因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素 0和+1,而不含有-1,因为此时不区分边的起点和终点。又如,在邻接表和星形表示 法中,每条边会被存储两次,而且反向星形表示显然是没有必要的,等等。 2.7轨与连通 W=ve1"e2…evk’其中e∈E(G),l≤i≤k,v∈(G),0≤j≤k,e与 v-1,v关联,称W是图G的一条道路(wak),k为路长,顶点v和v分别称为W的起 点和终点,而v1,V2,…,V称为它的内部顶点。 若道路W的边互不相同,则W称为迹rai)若道路W的顶点互不相同,则W称 为轨(path) 称一条道路是闭的,如果它有正的长且起点和终点相同。起点和终点重合的轨叫做 圈( cycle) 若图G的两个顶点u,v间存在道路,则称和ν连通( connected)。l,v间的最短轨 的长叫做l,v间的距离。记作d(u,v)。若图G的任二顶点均连通,则称G是连通图 显然有:
-50- 起始地址 rpoint(i) 1 1 3 6 8 9 记录弧信息的数组 弧编号 1 2 3 4 5 6 7 8 终点 2 2 3 3 3 4 4 5 起点 3 1 1 4 5 5 2 4 权 4 8 9 0 6 7 6 3 如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧， 则可以综合采用前向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以 只用一个数组（trace）记录一条弧在两种表示法中的对应关系即可。例如，可以在采用 前向星形表示法的基础上，加上上面介绍的 rpoint 数组和如下的 trace 数组即可。这相 当于一种紧凑的双向星形表示法如下所示： 两种表示法中的弧的对应关系（记为 trace ） 反向法中弧编号 j 1 2 3 4 5 6 7 8 正向法中弧编号 trace( j) 4 1 2 5 7 8 3 6 对于网络图的表示法，我们作如下说明： ① 星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的 优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FORTRAN 语言 等）也容易实现。邻接表表示法对那些提供指针类型的语言（如 C 语言等）是方便的， 且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工 作量较大（需要花费 O(m) 的计算时间）。有关“计算时间”的观念是网络优化中需要 考虑的一个关键因素。 ② 当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示 法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。 ③ 上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有 方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半 信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素 0 和 +1 ，而不含有 −1 ，因为此时不区分边的起点和终点。又如，在邻接表和星形表示 法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。 2.7 轨与连通 k k W v e v e e v = 0 1 1 2 ，其中 e E(G) i ，1 i k ，v V(G) j ，0 j k ， i e 与 i i v ,v −1 关联，称 W 是图 G 的一条道路(walk)，k 为路长，顶点 0 v 和 k v 分别称为 W 的起 点和终点，而 1 2 1 , , , k − v v v 称为它的内部顶点。 若道路 W 的边互不相同，则 W 称为迹(trail)。若道路 W 的顶点互不相同，则 W 称 为轨(path)。 称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做 圈(cycle)。 若图 G 的两个顶点 u, v 间存在道路，则称 u 和 v 连通(connected)。u, v 间的最短轨 的长叫做 u, v 间的距离。记作 d(u, v) 。若图 G 的任二顶点均连通，则称 G 是连通图。 显然有：