图的定义和术语

1、第第7 7章章 图图目录目录v图的定义和术语v图的存储结构v图的遍历v图的连通性问题v有向无环图及其应用v最短路径245136G17.1 图的定义和术语图的定义和术语v图被广泛地用于模拟真实事件或抽象问题。在语言学、逻辑学、物理、化学、电讯工程、计算机、数学等学科领域得到了广泛的应用。网络连接图例网络连接图例v图是由顶点集合V及顶点间的关系集合E组成的一种数据结构： Graph( V, E ) 任意一对顶点间都可以有关系；图是最基本的数据结构，树和线性表可看作受限图。7.1 图的定义和术语图的定义和术语245136G17.1 图的定义和术语图的定义和术语v有向图与无向图 在有向图中，顶点对是有

2、序的。在无向图中，顶点对(x, y)是无序的。例例245136G1例例157324G267.1 图的定义和术语图的定义和术语v完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。213有向完全图有向完全图213无向完全图无向完全图7.1 图的定义和术语图的定义和术语v邻接顶点 如果 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。v顶点 v 的入度 是以 v 为终点的有向边的条数顶点 v 的出度 是以 v 为始点的有向边的条数2451367.1 图的定义和术语图的定义和术语v

3、权某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。7.1 图的定义和术语图的定义和术语v子图设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。7.1 图的定义和术语图的定义和术语v简单路径若路径上各顶点 v1,v2,.,vm 均不互相重复, 则称这样的路径为简单路径。v回路若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。7.1 图的定义和术语图的定义和术语连通图 图中任意两个顶点都有路径强连通图 在有向图中, 每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径连通图连通图例例2451

4、36强连通图强连通图356例例7.1 图的定义和术语图的定义和术语连通分量 非连通图的极大连通子图7.1 图的定义和术语图的定义和术语v生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。但有向图则可能得到它的由若干有向树组成的生成森林。7.1 图的定义和术语图的定义和术语v图的基本操作CreateGraph(&G,V,VR); / 按V和VR的定义构造图G。DestroyGraph(&G); / 销毁图G。 LocateVex(G, u); / 查找顶点u GetVex(G, v); / 返回v的值。PutVex(&G, v, value)

5、; / 对v赋值value。FirstAdjVex(G, v); / 返回v的第一个邻接点 NextAdjVex(G, v, w); /返回v的下一个邻接点。 245136 7.1 图的定义和术语图的定义和术语v图的基本操作(续）InsertVex(&G, v); / 在图G中增添新顶点v。DeleteVex(&G, v); / 删除G中顶点v及其相关的弧。 InsertArc(&G, v, w); / 在G中增添弧， DeleteArc(&G, v, w); /在G中删除弧， DFSTraverse(G, v, Visit(); / 从顶点v起深度优先遍历图

6、BFSTraverse(G, v, Visit(); / 从顶点v起广度优先遍历图245136 7.2 图的存储结构图的存储结构v图的数组（邻接矩阵）存储表示图的数组（邻接矩阵）存储表示 用一个矩阵表示图结构用一个矩阵表示图结构，其它0E(G)v,v或)v,(v若1,jijijiA例例G1241300011000000001107.2.1 图数组表示法图数组表示法v网络的邻接矩阵网络的邻接矩阵 ),( , ,),( .jijiEjiEjijijiWjiEdge=! !0=A对角线但是否则,或且如果7.2.1 图数组表示法图数组表示法v在有向图中在有向图中, , 统计第统计第 i i 行行 1

7、1 的个数可得顶点的个数可得顶点 i i 的的出度，统计第出度，统计第 j j 行行 1 1 的个数可得顶点的个数可得顶点 j j 的入度。的入度。v在无向图中在无向图中, , 统计统计1 1 的个数可得的个数可得边的个数的两倍。边的个数的两倍。7.2.1 图数组表示法图数组表示法v无向图的邻接矩阵是对称矩阵无向图的邻接矩阵是对称矩阵7.2.1 图数组表示法图数组表示法v邻接矩阵存储结构邻接矩阵存储结构#define INF INT_MAX /最大值#define MAX_VER_NUM 20 /顶点个数typedef struct ElemType vexsMAX_VER_NUM; /顶点向

8、量 int arcsMAX_VER_NUMMAX_VER_NUM ;/邻接矩阵 int vexnum, arcnum; /图的顶点数和边数 int kind; /图的种类MGraph;7.2.1 图数组表示法图数组表示法v基本操作的实现基本操作的实现构造图构造图输入：边输入：边a,b 输出：邻接矩阵表示输出：邻接矩阵表示算法：算法：初始化邻接矩阵为初始化邻接矩阵为0 0； 输入一条边输入一条边a,b ； 令顶点令顶点a a的序号为的序号为i,i,设顶点设顶点b b的序号为的序号为j;j; 邻接矩阵的元素邻接矩阵的元素ijij=1=1； 重复重复-步，直到输入全部的边步，直到输入全部的边7.2

9、图的存储结构图的存储结构v邻接表邻接表用数组存储所有结点每个顶点采用一链表存储对应的所有邻接点7.2.2 图的邻接表图的邻接表v在有向图的邻接表中易于计算顶点的出度；在有向图的邻接表中易于计算顶点的出度；v计算顶点的入度，可采用逆连接表计算顶点的入度，可采用逆连接表7.2.2 图的邻接表图的邻接表v网络（带权图）的邻接表网络（带权图）的邻接表7.3 图的遍历图的遍历v从图中某一顶点出发访遍图中其余顶点，且从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫使每一个顶点仅被访问一次。这一过程就叫做做图的遍历图的遍历。v通常有两条遍历图的路径通常有两条遍历图的路径深度优先搜

10、索遍历深度优先搜索遍历广度优先搜索遍历广度优先搜索遍历7.3 图的遍历图的遍历7.3 图的遍历图的遍历v解决回路问题解决回路问题7.3 图的遍历图的遍历v解决不可到达问题解决不可到达问题7.3.1 图的深度优先搜索图的深度优先搜索v深度优先搜索遍历深度优先搜索遍历类似于树的先根遍历，是类似于树的先根遍历，是树的先根遍历的推广树的先根遍历的推广v思路：思路：从图中某个顶点从图中某个顶点V出发，访问此顶点出发，访问此顶点；然后依次从然后依次从V的未被访问的邻接点出发，深度优先遍历图，的未被访问的邻接点出发，深度优先遍历图，直至图中所有和直至图中所有和V有路径有路径的顶点都被访问到的顶点都被访问到；

11、若此时图中尚有顶点未被访问，则另选图中一个未曾被若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直至图中所有顶点访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止都被访问为止。7.3.1 图的深度优先搜索图的深度优先搜索7.3.1 图的深度优先搜索图的深度优先搜索DFS ( G, v) / 从第从第v个顶点出发递归地深度优先遍历图个顶点出发递归地深度优先遍历图G。 visitedv = TRUE; /访问访问 for (w=FirstAdjVex(v); w!=0; w=NextAdjVex(v) ) if (!visitedw) DFS (G, w)

12、; / 对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFS7.3.1 图的深度优先搜索图的深度优先搜索DFSTrav（）（） / 深度优先遍历。深度优先遍历。for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化访问标志数组初始化for (v=0; vvexnum; +v) / 从每个顶点出发调用从每个顶点出发调用DFS if (!visitedv) DFS (v, L);为不连通的图也能访问所有顶点，为不连通的图也能访问所有顶点，要从每个顶点出发，做深度优先要从每个顶点出发，做深度优先搜索，即调用搜索，即调用DFS(

13、).DFS( ).7.3.2 图的广度优先搜索图的广度优先搜索v度优先搜索遍历度优先搜索遍历类似于树的层次遍历类似于树的层次遍历 使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点 v v 之后，由之后，由 v v 出发，依次访问出发，依次访问 v v 的各个未曾被访问过的邻接顶点的各个未曾被访问过的邻接顶点 w w1, 1, w w2, 2, , , wtwt，然后再顺序访问，然后再顺序访问 w w1, 1, w w2, 2, , , wt wt 的所有还的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还

14、未被访问过的邻接顶点，访问它们的所有还未被访问过的邻接顶点， 如此做下如此做下去，直到图中所有顶点都被访问到为止。去，直到图中所有顶点都被访问到为止。7.3.2 图的广度优先搜索图的广度优先搜索v算法算法为了实现逐层访问，算法中使用了一个队列，以为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的顶点，以便于向下一层访问。记忆正在访问的顶点，以便于向下一层访问。与深度优先搜索过程一样，为避免重复访问，需与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组要一个辅助数组 visited ，给被访问过的顶点加，给被访问过的顶点加标记标记V1V2V4V5V3V7V6V87.3.2 图的广度优

15、先搜索图的广度优先搜索 for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化初始化 for ( v=0; vG.vexnum; +v ) /从每个顶点出发从每个顶点出发 if ( !visitedv) / v尚未访问尚未访问 visitedu = TRUE; EnQueue(Q,v); / v入队列入队列 while (!Q.queueEmpty( ) DeQueue(Q,u ); / 队头元素出队并赋给队头元素出队并赋给u for (w=FirstAdjVex(u); w!=0; w=NextAdjVex(u) ) /所有邻接点所有邻接点 if (

16、! visitedw) / u的尚未访问的邻接顶点的尚未访问的邻接顶点w入队列入队列Q visitedu = TRUE; EnQueue(Q,w); 7.3 图的遍历图的遍历v当无向图为非连通图时，从图中某一顶点出发，利用深度优当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图点，只能访问到该顶点所在的最大连通子图( (连通分量连通分量) )的所的所有顶点。有顶点。v若从无向图的每一个连通分量中的一个顶点出发进行遍历，若从无向图的每一个连通分量中的一个

17、顶点出发进行遍历，可求得无向图的所有连通分量。可求得无向图的所有连通分量。v在算法中，需要对图的每一个顶点进行检测：若已被访问过，在算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量问，则从该顶点出发遍历图，可求得图的另一个连通分量7.4 最小生成树最小生成树v问题：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？ 7.4 最小生成树v该问题等价于： 构造网的一棵最小生成树，

18、即：在e条带权的边中选取n-1条（不构成回路），使“权值之和”为最小。 7.4 最小生成树v最小生成树（MST）性质假设G=(V, E)是一个无向连通网，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边(u, v)的最小生成树顶点集合顶点集合U-V顶点集合顶点集合U7.4 最小生成树v普里姆算法的基本思想： 从连通网络 N = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。 以后每一步从一个顶点在U中，而另一个顶点在V-U中的各条边中选择权值最小的边(u, v),把它的

19、顶点加入到集合U中。 如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。普里姆算法构造最小生成树的过程普里姆算法构造最小生成树的过程24543424554347245543477普里姆算法构造最小生成树的过程（普里姆算法构造最小生成树的过程（ 续）续）245543472455434724554347v输入：无向联通图G=(V, E)v输出：最小生成树TE(U, TE)v算法：1.初始时任取一个顶点v，从v出发；此时U=v,TE= ;2.从顶点集U中取一顶点u0,从V-U集合中取一顶点v0,使边(u0,v0）权值最小；3.将该边加入到集合TE，并将u0并入U集合； 重复2、3步n

20、-1次。7.4.1 最小生成树Prim算法7.4 最小生成树vPrim算法的实现图的存储结构采用邻接矩阵7.4 最小生成树vPrim算法的实现(续)设置一个辅助数组closedge , 用于存放集合VU中的各顶点到集合中顶点的最小交叉边及其权值.typedef struct VertexType adjvex; /顶点 int lowcost; /边的权值 closedgeNUM; 0 1 2 3 4 5 6下标作为下标作为边的另一边的另一个端点个端点0,00,28 0, 0, 0, 0, 10 0, 0 1 2 3 4 5 6vPrim算法实现举例算法实现举例初始时，从初始时，从顶点顶点0出

21、发出发辅助数组closedge ：vPrim算法实现举例(续1)选一个最小选一个最小权值的边权值的边0,00,28 0, 0, 0, 0, 10 0, 0 1 2 3 4 5 6辅助数组closedge ：0输出边输出边(0,5),并将顶并将顶点点5加入加入U集合集合0,00,28 0, 0, 0, 0, 10 0, 0 1 2 3 4 5 60辅助数组closedge ：vPrim算法实现举例(续2)05更新数据：存储顶点更新数据：存储顶点0和和5出发的边中的小者出发的边中的小者0,00,28 0, 0, 0, 0, 00, 0 1 2 3 4 5 65,2505vPrim算法实现举例(续3

22、)又选一个最小的权值又选一个最小的权值0,00,28 0, 0, 5, 25 0, 00, 0 1 2 3 4 5 6vPrim算法实现举例(续4)05输出边输出边(5,4),并将并将顶点顶点4加入集合加入集合U0,00,28 0, 0, 5, 25 0, 00, 0 1 2 3 4 5 60054vPrim算法实现举例(续5)0,00,28 0, 0, 5, 00, 00, 0 1 2 3 4 5 6更新数据：增加顶点更新数据：增加顶点4出发的权值小的边出发的权值小的边4,224,24054vPrim算法实现举例(续6)0,00,28 0, 4, 22 5, 00, 04, 24 0 1 2

23、 3 4 5 6选一个最小的权值选一个最小的权值054vPrim算法实现举例(续7)0,00,28 0, 4, 22 5, 00, 04, 24 0 1 2 3 4 5 6输出边输出边(4,3),并将并将顶点顶点3加入集合加入集合U0vPrim算法实现举例(续8)05430,00,28 0, 4, 05, 00, 04, 24 0 1 2 3 4 5 6更新数据：增加顶点更新数据：增加顶点3出发的权值小的边出发的权值小的边3,123,180543vPrim算法实现举例(续9)0,00,28 3, 12 4, 05, 00, 03, 18 0 1 2 3 4 5 6选最小的权值选最小的权值vPr

24、im算法实现举例(续10)05430,00,28 3, 12 4, 05, 00, 03, 18 0 1 2 3 4 5 6输出边输出边(3,2),并将并将顶点顶点2加入集合加入集合U00543vPrim算法实现举例(续11)2054320,00, 28 3, 04, 05, 00, 03, 18 0 1 2 3 4 5 6更新数据：增加顶点更新数据：增加顶点2出发的权值小的边出发的权值小的边2,16vPrim算法实现举例(续12)0,02, 16 3, 04, 05, 00, 03, 18 0 1 2 3 4 5 6选最小的权值选最小的权值05432vPrim算法实现举例(续13)0,02,

25、 16 3, 04, 05, 00, 03, 18 0 1 2 3 4 5 6输出边输出边(2,1),并将并将顶点顶点1加入集合加入集合U0vPrim算法实现举例(续14)0543210,02, 03, 04, 05, 00, 03, 18 0 1 2 3 4 5 6更新数据：增加顶点更新数据：增加顶点1出发的权值小的边出发的权值小的边1,14054321vPrim算法实现举例(续15)0,02, 03, 04, 05, 00, 01, 14 0 1 2 3 4 5 6最后，最小的权值为最后，最小的权值为边边(1,6)，输出该边，输出该边0543216vPrim算法实现举例(续16)7.4.1

26、 最小生成树Prim算法v1. 1. 初始化辅助数组初始化辅助数组closedge ；v2. 2. 输出顶点输出顶点v v，将顶点，将顶点v v加入集合加入集合U U中；中；v3. 3. 重复执行下列操作重复执行下列操作n-1n-1次次 在在lowcostlowcost中选取最短边，取中选取最短边，取adjvexadjvex中对应的顶中对应的顶点序号点序号k k； 输出顶点输出顶点k k和对应的权值；和对应的权值； 将顶点将顶点k k加入集合加入集合U U中；中； 调整数组调整数组lowcostlowcost和和adjvexadjvex；7.4.1 最小生成树Prim算法 k = Locate

27、Vex ( G, u ); / / 顶点顶点u u为构造生成树的起始点为构造生成树的起始点 for ( j=0; jG.vexnum; +j ) / / 辅助数组初始化辅助数组初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / / 初始，初始，U Uuu for (i=0; iG.vexnum; +i) /在其余顶点中选择在其余顶点中选择 k = minimum(closedge); / / 选最小边选最小边 printf(closedgek.adjvex, G.vexsk); / / 输出该边输出该边 cl

28、osedgek.lowcost = 0; /并将顶并将顶k k加入加入U U集集 for (j=0; jG.vexnum; +j) /更新辅助数组更新辅助数组 if (G.arcskj.adj closedgej.lowcost) / / 新顶点并入新顶点并入U U后重新选择最小边更新辅助数组后重新选择最小边更新辅助数组 closedgej = G.vexsk, G.arcskj.adj ; 时间复杂度O(n2)7.4.1 最小生成树Kruskal算法v基本思想基本思想 每次选不属于同一连通分量每次选不属于同一连通分量( (保证不产生回路保证不产生回路) )且权值最小的边，加入且权值最小的边，

29、加入MSTMST。并将所在的。并将所在的2 2个连通分个连通分量合并，直到只剩一个连通分量量合并，直到只剩一个连通分量时间复杂度时间复杂度O(elogeO(eloge) )KruskalKruskal算法最小生成树的过程算法最小生成树的过程7.5 有向无环图及其应用v有向无环图（有向无环图（DAG)DAG) 不存在回路的有向图不存在回路的有向图vAOVAOV网网一个表示工程或系统的一个表示工程或系统的DAGDAG，用顶点表示活动，用顶点表示活动，用弧表示活动之间的优先关系，称为用弧表示活动之间的优先关系，称为AOVAOV网。网。vAOVAOV网的特点网的特点AOV网中的弧表示活动之间存在的某种

30、制约关系。网中的弧表示活动之间存在的某种制约关系。AOV网中不能出现回路网中不能出现回路 。7.5 有向无环图及其应用vAOVAOV网举例网举例一个课程安排系统一个课程安排系统7.5 有向无环图及其应用v拓扑排序拓扑排序 问题问题: : 1.1.假设以有向图表示一个工程的施工图或程序的数假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。据流图，则图中不允许出现回路。 2. 2. 检查有向图中是否存在回路的方法之一，是对检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。有向图进行拓扑排序。 7.5.1 拓扑排序何谓何谓“拓扑排序拓扑排序”？ 按照有向图给出的次序关

31、系，将图中顶点排成按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。顶点，则可以人为加上任意的次序关系。 AOV网拓扑排序7.5.1 7.5.1 拓扑排序拓扑排序v如何进行拓扑排序？如何进行拓扑排序？ 1.1.从有向图中选取一个没有前驱的顶点，并输出之从有向图中选取一个没有前驱的顶点，并输出之; ; 2. 2.从有向图中删去该顶点出发的所有边从有向图中删去该顶点出发的所有边; ; 重复上述两步，直至图空，或者找不到无前驱重复上述两步，直至图空，或者找不到无前驱的顶点为止。的顶点为止

32、。7.5.1 拓扑排序拓扑排序v拓扑排序算法实现拓扑排序算法实现 1.1.从有向图中选取一个没有前驱的顶点，并输出之从有向图中选取一个没有前驱的顶点，并输出之; ; 2. 2.从有向图中删去该顶点出发的所有边从有向图中删去该顶点出发的所有边; ; 重复上述两步，直至图空，或者找不到无前驱重复上述两步，直至图空，或者找不到无前驱的顶点为止。的顶点为止。入度为入度为0 0的顶点的顶点邻接点的入度减邻接点的入度减1degreefirstarcvexsdata7.5.1 拓扑排序拓扑排序v拓扑排序算法拓扑排序算法1.1.计算顶点的入度计算顶点的入度degree ;degree ;2.2.统计输出的顶点

33、数统计输出的顶点数count=0;count=0;3. 3. whilewhile（有入度为零的顶点）（有入度为零的顶点） 选一个入度为零的顶点选一个入度为零的顶点k;k; 输出输出k;k; 删除顶点删除顶点k;k; count+; count+; for (k for (k的所有邻接点的所有邻接点) ) 入度减入度减1 1； 4.if (count4.if (count顶点数顶点数) ) 存在环；存在环；时间复杂度为时间复杂度为 O(e+n)7.5.1 拓扑排序拓扑排序 Status Top-Sort(ALGraph G) /对图对图G G进行拓扑排序进行拓扑排序 FindInDegree(

34、G，indegree)； /计算顶点入度计算顶点入度indegree indegree count=0; /统计输出的顶点统计输出的顶点 for(i=0；iG.vexnum； +i) if (degreei=0) break; /选入度为零的顶点选入度为零的顶点 while (inext) k=p-vexs； /i/i的邻接点的邻接点k k -indegreek /入度减入度减1 1 if (countG.vexnum) return ERROR； /有回路有回路 else return OK； 7.5.1 拓扑排序拓扑排序v拓扑排序的用途拓扑排序的用途1.1.将有向无环图中的顶点线性化将有向

35、无环图中的顶点线性化2.2.检测一个有向图中是否存在环检测一个有向图中是否存在环7.5.2 关键路径关键路径v 问题问题: : 假设以有向网表示一个施工流图（假设以有向网表示一个施工流图（AOEAOE网），网）， 顶点表示事件，弧表示活动，弧上的权值表示完成顶点表示事件，弧表示活动，弧上的权值表示完成该项活动所需时间，该项活动所需时间， 问问: :1.1. 完成整个工程至少需要多少时间完成整个工程至少需要多少时间? ?2. 2. 为缩短完成工程所需的时间为缩短完成工程所需的时间, , 应当加快哪些活动应当加快哪些活动? ?7.5.2 关键路径关键路径v整个工程完成的时间整个工程完成的时间 从有

36、向图的源点到汇点的最长路径。从有向图的源点到汇点的最长路径。v 关键活动关键活动 最长路径上的活动最长路径上的活动 7.5.2 关键路径关键路径v如何求关键活动？如何求关键活动？ 活动的最早开始时间活动的最早开始时间 e e(i(i) ) 活动的最迟开始时间活动的最迟开始时间 l l(i(i) ) 关键活动为：关键活动为： e(ie(i)=l(i)=l(i)如：如：e(a4)=6, l(a4)=6e(a4)=6, l(a4)=6 e(a9)=7, l(a9)=6+3 e(a9)=7, l(a9)=6+3 jkai987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9

37、a8=7a10=2a11=47.5.2 关键路径关键路径v如何求关键活动（续如何求关键活动（续1）？）？计算各个活动的计算各个活动的e(i)与与 l(i)，以判别是否，以判别是否l(i)= e(i).为求为求e(i)与与l(i)，需要先求得各顶点最早发生时间，需要先求得各顶点最早发生时间Ve( ) 和最晚发生时间和最晚发生时间Vl( )显然，显然，e(i)=ve(j)；l(i)=vl(k)-dutai的权值的权值jkai7.5.2 关键路径关键路径v如何求关键活动（续如何求关键活动（续2）？）？ 如何计算如何计算veve( )( )和和 vlvl( )?( )? 从从Ve(0)=0开始向前递推

38、开始向前递推 ve(k) = Maxve(j) + dut() 从从Vl(n)=Ve(n)开始向后递推开始向后递推 vl(j) = Minvl(k) dut() jkjj. jkkk这两个递推公式必须分别在拓扑有序及拓扑逆序下进行。这两个递推公式必须分别在拓扑有序及拓扑逆序下进行。7.5.2 关键路径关键路径v求关键活动的实现要点求关键活动的实现要点按拓扑有序计算ve;按拓扑逆序计算vl;为求拓扑逆序序列，应在拓扑排序时，用 “栈栈”存储拓扑有序序列。 7.6 最短路径最短路径v问题的提出问题的提出 要在计算机上建立一个交通咨询系统（图结构）要在计算机上建立一个交通咨询系统（图结构）顶点表示城

39、市顶点表示城市边表示两个城市的交通联系边表示两个城市的交通联系v最短路径问题最短路径问题 从一个顶点到达另一个顶点，从一个顶点到达另一个顶点，如何找到一条最短的路径？如何找到一条最短的路径？7.6 最短路径最短路径v问题解决问题解决单源点最短路径问题单源点最短路径问题 顶点对之间的最短路径顶点对之间的最短路径 Floyd Floyd算法算法7.6.1 单源点问题单源点问题v问题的提法问题的提法 从某一顶点出发，到其它各顶点的最短路径从某一顶点出发，到其它各顶点的最短路径7.6.1 单源点问题单源点问题vDijkstraDijkstra算法算法 按按路径长度递增路径长度递增的次序求从源点到其余各

40、点最的次序求从源点到其余各点最短路径的算法短路径的算法首先求出长度最短的一条最短路径首先求出长度最短的一条最短路径再参照它求出长度次短的一条最短路径再参照它求出长度次短的一条最短路径依次类推，直到从顶点依次类推，直到从顶点v v到其它各顶点的最短路径全部求到其它各顶点的最短路径全部求出为止出为止7.6.1 单源点问题单源点问题vDijkstraDijkstra算法算法 假设图中所示为从源点到其余各点之间的最短路径，假设图中所示为从源点到其余各点之间的最短路径，则在这些路径中，必然存在一条长度最短者则在这些路径中，必然存在一条长度最短者 在这条路径上，必定只含一条权值最小弧。由此，只要在这条路径

41、上，必定只含一条权值最小弧。由此，只要在所有从源点出发的弧中查找权值最小者在所有从源点出发的弧中查找权值最小者; ; 长度次短的路径可能有两种情况长度次短的路径可能有两种情况: : 它可能是从源点直接到该点的路径它可能是从源点直接到该点的路径; ; 也可能是，从源点到也可能是，从源点到a, a, 再从再从a a到该点到该点 其余依次类推其余依次类推源点源点a7.6.1 单源点问题单源点问题vDijkstraDijkstra算法的基本过程算法的基本过程1.1.初始时，初始时，S S只包含源点只包含源点v v。U U包含除包含除v v外的其他顶点。外的其他顶点。2.2.从从U U中选取一个距离中选

42、取一个距离v v最小的顶点最小的顶点k k，把，把k k加入加入S S中（该中（该选定的距离就是选定的距离就是v v到到k k的最短路径长度）。的最短路径长度）。3.3.以以k k为新考虑的中间点，修改为新考虑的中间点，修改U U中各顶点的距离中各顶点的距离: :若从若从源点源点v v到顶点到顶点u u（u u U U）的距离（经过顶点）的距离（经过顶点k k）比原来距）比原来距离（不经过顶点离（不经过顶点k k）短，则修改顶点）短，则修改顶点u u的距离值。的距离值。 重复步骤重复步骤2.2.和和3.3.直到所有顶点都包含在直到所有顶点都包含在S S中。中。路径长度递增的次序路径长度递增的次序7.6.1 单源点问题单源点问题vDijkstra算法的实现算法的实现引入一个辅助数组引入一个辅助数组distdist。它的每一个分量。它的每一个分量distidisti 表表示当前所确定的从源点示当前所确定的从源点v v0 0到终点到终点vivi 的最短路径的长度的最短路径的长度 显然，显然， DistiDisti = = 或者或者 = = + + 初始