8-[39 这是一个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)、(54),他们对应的权分别为6和7。 对于有向图G=(V,4),一般用A(1)表示节点i的邻接表,即节点i的所有出弧构 成的集合或链表(实际上只需要列出弧的另一个端点,即弧的头)。例如上面例子 A(1)={2,3},A(5)={34}等。 (v)星形表示法 星形(star)表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点 它也是记录从该节点出发的所有弧,但它不是采用单向链表而是采用一个单一的数组表 示。也就是说,在该数组中首先存放从节点1出发的所有弧,然后接着存放从节点2 出发的所有孤,依此类推,最后存放从节点n出发的所有孤。对每条弧,要依次存放其 起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号 只是从同一节点出发的弧的顺序可以任意排列。此外,为了能够快速检索从每个节点出 发的所有弧,我们一般还用一个数组记录每个节点出发的弧的起始地址(即弧的编号)。 在这种表示法中,可以快速检索从每个节点出发的所有弧,这种星形表示法称为前向星 形( forward star)表示法。 例如,在例7所示的图中,仍然假设弧(1,2),(1,3),(2,4),(3,2),(4,3),(4,5), (5,3)和(5,4)上的权分别为8,9,6,4,0,3,6和7。此时该网络图可以用前向 星形表示法表示为表2和表3。 表2节点对应的出弧的起始地址编号数组 节点号 起始地址poin() ,十 表3记录弧信息的数组 弧编号 起点1 终点 4324 权 03 在数组 point中,其元素个数比图的节点数多1(即n+1),且一定有poin(1)=1, poin(n+1)=m+1。对于节点i,其对应的出弧存放在弧信息数组的位置区间为 Ipoint (i, point(i+1)-1 如果poin()=poin(+1),则节点i没有出弧。这种表示法与弧表表示法也非常相
-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 没有出弧。这种表示法与弧表表示法也非常相
似,“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中, 弧被编号后有序存放,并增加一个数组( point)记录每个节点出发的弧的起始编号。 前向星形表示法有利于快速检索每个节点的所有出弧,但不能快速检索每个节点的 所有入弧。为了能够快速检索每个节点的所有入孤,可以采用反向星形( reverse star) 表示法:首先存放进入节点1的所有孤,然后接着存放进入节点2的所有弧,依此类推 最后存放进入节点n的所有孤。对每条弧,仍然依次存放其起点、终点、权的数值等有 关信息。同样,为了能够快速检索从每个节点的所有入弧,我们一般还用一个数组记录 每个节点的入孤的起始地址(即弧的编号)。例如,例7所示的图,可以用反向星形表 示法表示为表4和表5 表4节点对应的入弧的起始地址编号数组 节点号i 起始地址 upon() 表5记录弧信息的数组 弧编号 终点2 主 如果既希望快速检索每个节点的所有出弧,也希望快速检索每个节点的所有入弧 则可以综合采用前向和反向星形表示法。当然,将孤信息存放两次是没有必要的,可以 只用一个数组( trace)记录一条弧在两种表示法中的对应关系即可。例如,可以在采用 前向星形表示法的基础上,加上上面介绍的 point数组和如下的 trace数组即可。这相 当于一种紧凑的双向星形表示法,如表6所示。 表6两种表示法中的弧的对应关系 反向法中弧编号j 正向法中弧编号 trace() 对于网络图的表示法,我们作如下说明: ①星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的 优点是占用的存储空间较少,并且对那些不提供指针类型的语言(如 FORTRAN语言 等)也容易实现。邻接表表示法对那些提供指针类型的语言(如C语言等)是方便的, 且增加或删除一条弧所需的计算工作量很少,而这一操作在星形表示法中所需的计算工 作量较大(需要花费O(m)的计算时间)。有关“计算时间”的观念是网络优化中需要 考虑的一个关键因素。 ②当网络不是简单图,而是具有平行弧(即多重弧)时,显然此时邻接矩阵表示 法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形 ③上述方法可以很方便地推广到可以处理无向图的情形,但由于无向图中边没有 方向,因此可能需要做一些自然的修改。例如,可以在计算机中只存储邻接矩阵的一半 信息(如上三角部分),因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素 0和+1,而不含有-1,因为此时不区分边的起点和终点。又如,在邻接表和星形表示 法中,每条边会被存储两次,而且反向星形表示显然是没有必要的,等等。 27轨与连通 W=veve2…e"k,其中e∈E(G),1≤i≤k,"∈H(G),0≤j≤k,e与
-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 与
v-1,v2关联,称W是图G的一条道路(wak),k为路长,顶点v和v分别称为W的起 点和终点,而v1,v2,…,vk称为它的内部顶点 若道路W的边互不相同,则W称为迹rai)。若道路W的顶点互不相同,则W称 为轨(path) 称一条道路是闭的,如果它有正的长且起点和终点相同。起点和终点重合的轨叫做 圈( cycle) 若图G的两个顶点l,v间存在道路,则称l和v连通( connected)。a,间的最短轨 的长叫做u,v间的距离。记作d(l,v)。若图G的任二顶点均连通,则称G是连通图 显然有 (i)图P是一条轨的充要条件是P是连通的,且有两个一度的顶点,其余顶点的度 为2 (in)图C是一个圈的充要条件是C是各顶点的度均为2的连通图 §3应用一最短路问题 3.1两个指定顶点之间的最短路径 问题如下:给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间 找一条最短铁路线 以各城镇为图G的顶点,两城镇间的直通铁路为图G相应两顶点间的边,得图G 对G的每一边e,赋以一个实数w(e)一直通铁路的长度,称为e的权,得到赋权图G。 G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点l0,vo 间的具最小权的轨。这条轨叫做0,v间的最短路,它的权叫做l,V间的距离,亦记 作d(l0,vo)。 求最短路已有成熟的算法:迪克斯特拉( Dijkstra)算法,其基本思想是按距从 近到远为顺序,依次求得础到G的各顶点的最短路和距离,直至v(或直至G的所有 顶点),算法结束。为避免重复并保留每一步的计算信息,采用了标号算法。下面是该 算法。 ()令Ⅳ(l)=0,对v≠L0,令l(v)=∞,S0={u0},i=0。 (i)对每个v∈S(S=\S,,用 min I(v),/(u+w(uv) 代替Ⅳ(ν)。计算min{()},把达到这个最小值的一个顶点记为u1+1,令 S=SU{l41}。 (i)若i=|-1,停止;若i<V|-1,用i+1代替i,转(in) 算法结束时,从到各顶点v的距离由ν的最后一次的标号l(v)给出。在v进入S 之前的标号1(v)叫T标号,v进入S时的标号l(v)叫P标号。算法就是不断修改各顶 点的T标号,直至获得P标号。若在算法运行过程中,将每一顶点获得P标号所由来 的边在图上标明,则算法结束时,u至各项点的最短路也在图上标示出来了。 例9某公司在六个城市c1,C2,…,C6中有分公司,从c到c的直接航程票价记在 下述矩阵的(i,j)位置上。(∞表示无直接航路),请帮助该公司设计一张城市c1到其它
-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 到其它
城市间的票价最便宜的路线图 0015 o1501020∞ 40201001025 2010055 1025∞25550 用矩阵anxn(n为顶点个数)存放各边权的邻接矩阵,行向量pb、 index1、 index2 d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分 当第顶点已标号 pb(i) l0当第/顶点未标号 index2()存放始点到第i点最短通路中第i顶点前一顶点的序号; d(i)存放由始点到第i点最短通路的值。 求第一个城市到其它城市的最短路径的 Matlab程序如下 clc, clear a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10 (2,3)=15;a(2,4)=20;a(2,6)=25; a(4,5)=10;a(4,6)=25 a(5,6)=55 a(find(a==0))=inf pb(1: length(a))=0;pb(1)=l;index=liindex2=ones(l, length(a)) d(l: length(a))=inf;d(1)=0; temp=1 while sum(pb)<length(a) th=find(pb==0)i tmpb=find(d(tb)==min(d(tb)/ tb)); d(tb)=min(d(tb), d(temp)+a(ter temp=tb( tmpb(1))i pb(temp)=li ndexl=[index, temp]i temp2=find(d(index1)==d(temp)-a(temp, index1)) index2(temp)=index1(temp2(1)) end index, index2 3.2两个指定顶点之间最短路问题的数学表达式 假设有向图有n个顶点,现需要求从顶点1到顶点n的最短路。设H=(W9)m为 赋权邻接矩阵,其分量为 vy,∈E 其它
-76- 城市间的票价最便宜的路线图。 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ∞ ∞ ∞ ∞ ∞ ∞ 10 25 25 55 0 25 20 10 0 55 40 20 10 0 10 25 15 0 10 20 50 0 15 20 25 0 50 40 25 10 用矩阵an×n （n 为顶点个数）存放各边权的邻接矩阵，行向量 pb、 1 index 、 2 index 、 d 分别用来存放 P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分 量 ⎩ ⎨ ⎧ = 当第 顶点未标号 当第 顶点已标号 i i pb i 0 1 ( ) ； ( ) 2 index i 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； d(i) 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的 Matlab 程序如下： clc,clear a=zeros(6); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a'; a(find(a==0))=inf; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0;temp=1; while sum(pb)<length(a) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; index1=[index1,temp]; temp2=find(d(index1)==d(temp)-a(temp,index1)); index2(temp)=index1(temp2(1)); end d, index1, index2 3.2 两个指定顶点之间最短路问题的数学表达式 假设有向图有 n 个顶点，现需要求从顶点 1 到顶点 n 的最短路。设W = wij n×n ( ) 为 赋权邻接矩阵，其分量为 ⎩ ⎨ ⎧ ∞ ∈ = , 其它 w(v v ), v v E w i j i j ij
决策变量为x,当x=1,说明弧v,位于顶点1至顶点n的路上:否则x=0。其 数学规划表达式为 min ,∈E ∑x-∑x,={-1 xn=0或1 例10在图3中,用点表示城市,现有A,B1,B2C1,C2,C3,D共7个城市。点与 点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市A 到城市D铺设一条天然气管道,请设计出最小价格管道铺设方案。 图37个城市间的连线图 编写 LINGO程序如下 model ets: ities/ A, B1, B2, C1, C2, C3, D/; roads(cities, cities)/A Bl A B2, b1 Cl bl C2, Bl C3, B2 Cl, B2 C2, B2 C3, C1 D, C2 D, C3 D/: W,xi endsets W=24331231134 nddat n=8size( citles);!城市的个数; min=@sum (roads: w*x) @for(cities(i)li #ne1 and# i #ne#n @sum(roads(1,3):x(1,3))=@sum(roads (3, 1): x(3, 1))) @sum(roads(i,3)li #eq#1: x(1,3))=1 @sum(roads(1,3)13#eg#n: x(i,3))=l; end 例11(无向图的最短路问题)求图4中v1到v1的最短路。 分析例10处理的问题属于有向图的最短路问题,本例是处理无向图的最短路问 题,在处理方式上与有向图的最短路问题有一些差别,这里选择赋权邻接矩阵的方法编 写 LINGO程序
-77- 决策变量为 ij x ，当 xij = 1，说明弧 i j v v 位于顶点 1 至顶点 n 的路上；否则 xij = 0。其 数学规划表达式为 ∑v v ∈E ij ij i j min w x s.t. ⎪ ⎩ ⎪ ⎨ ⎧ ≠ − = = ∑ − ∑ = ∈ = ∈ = i n i n i x x n v v E j ji n v v E j ij i j j i 0, 1, 1, 1, 1 1 1 xij = 0 或1 例 10 在图 3 中，用点表示城市，现有 A, B1, B2 ,C1,C2 ,C3 , D 共 7 个城市。点与 点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市 A 到城市 D 铺设一条天然气管道，请设计出最小价格管道铺设方案。 图 3 7 个城市间的连线图 编写 LINGO 程序如下： model: sets: cities/A,B1,B2,C1,C2,C3,D/; roads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1, B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x; endsets data: w=2 4 3 3 1 2 3 1 1 3 4; enddata n=@size(cities); !城市的个数; min=@sum(roads:w*x); @for(cities(i)|i #ne#1 #and# i #ne#n: @sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i))); @sum(roads(i,j)|i #eq#1:x(i,j))=1; @sum(roads(i,j)|j #eq#n:x(i,j))=1; end 例 11（无向图的最短路问题）求图 4 中 1 v 到 11 v 的最短路。 分析 例 10 处理的问题属于有向图的最短路问题，本例是处理无向图的最短路问 题，在处理方式上与有向图的最短路问题有一些差别，这里选择赋权邻接矩阵的方法编 写 LINGO 程序