《数学模型与数学实验》课程书籍文献（数学建模算法大全）第05章图与网络.pdf_P6-P10

-73- 这是一个 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}等。（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。此时该网络图可以用前向星形表示法表示为表 2 和表 3 。表 2 节点对应的出弧的起始地址编号数组节点号i 1 2 3 4 5 6 起始地址 point(i) 1 3 4 5 7 9 表 3 记录弧信息的数组弧编号 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 没有出弧。这种表示法与弧表表示法也非常相

似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中亮被编号后有序存放，并增加一个数组(DO1)记录每个节点出发的弧的起始编号前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形(reverse star) 表示法：首先存放进入节点1的所有孤，然后接着存放进入节点2的所有弧，依此类推后存放人节点n的不节点的地址（即弧的编号。例如，例7所示的图。可以用反向示为表4和表5 表4节点对应的入弧的起始地址编号数组节点号i 2 3 4 56 起始地址rpoint() 3 689 表5记录弧信息的数组 3 。起点31 45524 如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧则可以综合采用前向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以只用一个数组(tc心)记录一条弧在两种表示法中的对应关系即可。例如，可以在采用前向星形表示法的基础上，加上上面介绍的poi数组和如下的race数组即可.这相当于一种紧凑的双向星形表示法，如表6所示。表6两种表示法中的弧的对应关系反向法中弧编号 12345678 正向法中弧编号race() 41257836 对于网络图的表示法，我们作如下说明和都表表示法在实际算法实现中都是经常采用的。星形表示法的储快指且增加或除需的计算工作量很少类型在星形 C语化中考虑的当不是简单图而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示法是不能采用的。甘法则可以很方便地推广到可以处理平行弧的情形 ③上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素 0和+1，而不含有-1，因为此时不区分边的起点和终点。又如，在邻接表和星形表示法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。 27轨与连通 W=eye2evg,其中e,∈EG),1si≤k,y,eV(G),0≤j≤k,e与 -74

-74- 似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中，弧被编号后有序存放，并增加一个数组（ point ）记录每个节点出发的弧的起始编号。前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star）表示法：首先存放进入节点 1 的所有孤，然后接着存放进入节点 2 的所有弧，依此类推，最后存放进入节点n 的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一般还用一个数组记录每个节点的入孤的起始地址（即弧的编号）。例如，例 7 所示的图，可以用反向星形表示法表示为表 4 和表 5。表 4 节点对应的入弧的起始地址编号数组节点号i 1 2 3 4 5 6 起始地址 rpoint(i) 1 1 3 6 8 9 表 5 记录弧信息的数组弧编号 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 数组即可。这相当于一种紧凑的双向星形表示法，如表 6 所示。表 6 两种表示法中的弧的对应关系反向法中弧编号 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 Le v = 0 1 1 2 ，其中e E(G) i ∈ ，1 ≤ i ≤ k ，v V (G) j ∈ ，0 ≤ j ≤ k ， i e 与

y,y,关联，称W是图G的一条道路(wak,k为路长，顶点，和y分别称为W的起点和终点，而，称为它的内部顶点。若道路W的边互不相同，则W称为迹(ri).若道路W的顶点互不相同，则W称为轨(pat 一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈(cy 图G的两个顶点，v间存在道路则称 ,间的最短到的长叫阿的距高，记作dL。若闲G的任点均造道则G是通显然有图P是一条轨的充要条件是P是连通的，且有两个一度的顶点，其余顶点的度为2 图C是一个圈的充要条件是C是各顶点的度均为2的连通图 $3应用一最短路问题 3.】两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G 对G的每一边e,赋以一个实数w(e)一直通铁路的长度，称为e的权，得到赋权图G。 G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点，。间的具最小权的轨。这条轨叫做，。间的最短路，它的权叫做4，。间的距离，亦记作d(4o,o) 求最短路已有成熟的算法：迪克斯特拉(Dijkstr)算法，其基本思想是按距山从近到远为顺序，依次求得到G的各顶点的最短路和距离，直至V。(或直至G的所有 (令(4)=0，对v≠4。，令()=0，S。={4,},1=0 (而对每个ve5(5=V八S),用 min(v)./(u)+w(u) 代替)。计算(}，把达到这个最小值的一个顶点记为1，令 S1=S,U{u}. (的.若i=V-l,停止：若iV-1,用i+1代替i,转（。算法结束时，从山，到各顶点v的距离由v的最后一次的标号(v)给出。在v进入S, 之前的标号()叫T标号，进入S,时的标号()叫P标号。算法就是不断修改各顶点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由米的边在图上标明，则算法结束时，4至各项点的最短路也在图上标示出来了。例9某公司在六个城市G,C2,c,中有分公司，从C,到c,的直接航程票价记在下述矩阵的（亿，）位置上。(0表示无直接航路)，请帮助该公司设计一张城市C到其它

-75- i i v ,v −1 关联，称W 是图G 的一条道路(walk)，k 为路长，顶点 0 v 和 k v 分别称为W 的起点和终点，而 1 2 1 , , , k − v v L v 称为它的内部顶点。若道路W 的边互不相同，则W 称为迹(trail)。若道路W 的顶点互不相同，则W 称为轨(path)。称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈(cycle)。若图G 的两个顶点u, v 间存在道路，则称u 和v 连通(connected)。u, v 间的最短轨的长叫做u, v 间的距离。记作d(u,v) 。若图G 的任二顶点均连通，则称G 是连通图。显然有： (i) 图 P 是一条轨的充要条件是 P 是连通的，且有两个一度的顶点，其余顶点的度为 2； (ii) 图C 是一个圈的充要条件是C 是各顶点的度均为 2 的连通图。 §3 应用—最短路问题 3.1 两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数 w(e) —直通铁路的长度，称为e 的权，得到赋权图G 。 G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点 0 0 u ,v 间的具最小权的轨。这条轨叫做 0 0 u ,v 间的最短路，它的权叫做 0 0 u ,v 间的距离，亦记作 ( , ) 0 0 d u v 。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0 从近到远为顺序，依次求得u0 到G 的各顶点的最短路和距离，直至 0 v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令l(u0 ) = 0，对 u0 v ≠ ，令l(v) = ∞ ， { } S0 = u0 ，i = 0。 (ii) 对每个 Si v ∈ （ Si V Si = \ ），用 min{l(v),l(u) w(uv)} i u S + ∈ 代替 l(v) 。计算 min{l(v)} i v∈S ，把达到这个最小值的一个顶点记为 ui+1 ，令 { } Si+1 = Si U ui+1 。 (iii). 若i =|V | −1，停止；若i <|V | −1，用i +1代替i ，转(ii)。算法结束时，从u0 到各顶点v 的距离由v 的最后一次的标号l(v) 给出。在v 进入 Si 之前的标号l(v) 叫 T 标号，v 进入 Si 时的标号l(v) 叫 P 标号。算法就是不断修改各顶点的 T 标号，直至获得 P 标号。若在算法运行过程中，将每一顶点获得 P 标号所由来的边在图上标明，则算法结束时，u0 至各项点的最短路也在图上标示出来了。例 9 某公司在六个城市 1 2 6 c , c ,L, c 中有分公司，从 i c 到 j c 的直接航程票价记在下述矩阵的(i, j) 位置上。（∞表示无直接航路），请帮助该公司设计一张城市 1 c 到其它

《数学模型与数学实验》课程书籍文献（数学建模算法大全）第05章 图与网络

《数学模型与数学实验》课程书籍文献（数学建模算法大全）第05章图与网络