第八章图GraphsTheeighthchapterGraphs.ppt

《第八章图GraphsTheeighthchapterGraphs.ppt》由会员分享，可在线阅读，更多相关《第八章图GraphsTheeighthchapterGraphs.ppt（109页珍藏版）》请在三一文库上搜索。

1、第七章图（Graphs),图的基本概念 图的存储表示 图的遍历 最小生成树 活动网络 最短路径,图例,结点,边: (v2, v5),图的构成： 结点集：V=v1,v2,v3,v4,v5, 边集： E=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),图例,有向边 V3：始点， v4: 终点,图的构成： 结点集：V=v1,v2,v3,v4, 有向边集：E=,图的概念,图是由顶点(vertex)集合及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非 空集合； E = | x, y

2、V 是顶点之间关系的有穷集合，也叫做边(edge)的集合。,有向图G1 V1=v1,v2,v3,v4, E1=, 无向图G2 V2=v1,v2,v3,v4,v5, E2=, , 或者 E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),(a) G1=(V1,E1),(b) G2 = (V2, E2),图的术语,v3邻接到v4,v4的入度 ID(v4)=1,v1的出度 OD(v4) = 1,性质: 入度之和 = 出度之和 = 边数,结点的度数: TD(v) = ID(v)+OD(v),v1和v4互为邻接点,v4的度数为2 TD(v4)=2,度数之

3、和 = 边数的二倍 （因为每个边“贡献”了两个度数）,子图 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。 权 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。,路径: (1) , (简单路径) (2) , , (环) (3) ,路径: 在图 G(V, E) 中, 若存在边的序列 (vi, vp1)、(vp1, vp2)、.、(vpm, vj) 则称顶点序列 ( vi vp1 v

4、p2 . vpm vj ) 为从顶点vi 到顶点 vj 的路径。,路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和,简单路径 若路径上各顶点 v1,v2,.,vm 均不互相重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。,连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。 如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。,强连通图 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj

5、和从vj到vi的路径, 则称此图是强连通图。,生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。,图的存储结构,邻接矩阵,存储原则: 存储结点集和边集的信息.,（1）存储结点集； （2）存储边集： 存储每两个结点是否有关系。,图的存储结构,有向图的邻接矩阵,带权图的邻接矩阵,邻接矩阵表示法,在图的邻接矩阵表示中: 有一个记录各个顶点信息的顶点表， 还有一个表示各个顶点之间关系的邻接矩阵。,#define MAX_VERTEX_NUM 20 /最大顶点个数 typedef struct VertexType vexsMAX_VERTEX_NUM； /顶点向量 int

6、 arcs MAX_VERTEX_NUM MAX_VERTEX_NUM ； /邻接矩阵 int vexnum，arcnum； /图的当前顶点数和弧数 MGraph;,容易计算结点的度数; 容易判定两个结点间是否有边相连; 容易判定结点之间是否有路径相连(计算Am); 对于有向图，需要n个单元存储结点数据， n*n个单元存储邻接矩阵； 无向图的邻接矩阵是对称的, 可以压缩存储; 存储量与结点数有关, 与边数无关; 若边数n2, 则邻接矩阵是稀疏矩阵;,邻接表,每个结点拉出一个邻接边链表 (以此结点为始点的所有邻接点),所有结点存储与一个表中,以A为始点的边链,以A为终点的边链,邻接表,图的邻接表

7、存储表示,#define MAX_VERTEX_NUM 20 typedef struct ArcNode/单链表结点结构 int adjvex； /该弧所指向的顶点的位置 struct ArcNode *nextarc； /指向下一条弧的指针 InfoType *info； /该弧相关信息的指针 ArcNode； typedef struct VNode /顶点结构 VertexType data； /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode，AdjListMAX_VERTEX_NUM,Typedef struct /邻接表结构 AdjLi

8、st vertices； int vexnum，arcnum； /图的当前顶点数和弧数 ALGraph；,顶点vi的度恰为第i个链表中的结点数； 在有向图中，第i个链表(出边表)中的结点个数是顶点的出度;,邻接表的特点,求入度必须遍历整个邻接表: 在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。 为了求入度的便利, 可以建立逆邻接表, 即链表为入边表;,设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。,邻接表,(B,D)边出现在D的边链表中,(B,D)边出现在B

9、的边链表中,如果以边为处理对象, 如删除一个边, 则需扫描每个结点的边表, 找到同一条边.,邻接多重表,将邻接表中代表同一个边的结点合并; 边表合并为多重表; 在邻接多重表中，每一条边只有一个边结点, 为有关边的处理提供了方便。,边结点结构：,mark: 记录是否处理过的标记; ivex, jvex: 该边的两顶点位置; ilink:指向下一条依附于顶点ivex的边； jlink: 指向下一条依附于顶点jvex的边。,mark ivex jverx ilink jlink,typedef emnu unvisited，visited Visited； typedef struct EBox V

10、isited mark； /访问标记 int ivex，jvex；/该边依附的两个顶点的位置 struct EBox *ilink，*jlink；/分别指向依附这两个顶点的下一条边 InfoType *info； /该边信息指针 EBox；,mark ivex jverx ilink jlink,data: 存放与该顶点相关的信息， firstedge: 指示第一条依附于该顶点的边的指针,顶点结点的结构：,data firstedge,typedef struct VexBox VertexType data； EBox *firstedge /指向第一条依附该顶点的边 VexBox；,typ

11、edef struct VexBox adjmulistMAX_VERTEX_NUM； int vexnum，edgenum； /无向图的当前顶点数和边数 AMLGraph;,图的抽象数据类型,ADT Graph 数据对象V： V是具有相同特性的数据元素的顶点集。 数据关系R： R=VR VR= | v，wV且P(v，w) ，谓词 P(v，w) 定义了弧的意义或信息 ,基本操作P： CreateGraph(&G，V，VR)； 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph(&G)； 初始条件：图G存在。 操作结果：销毁图G。,Fi

12、rstAdjVex(G，v)； 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中 没有邻接顶点，则返回“空”。,InsertVex(&G，v)； 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex(&G，v)； 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。,NextAdjVex(G，v，w)； 初始条件：图G存在，v是G中某个顶点， w是v的邻接顶点。 操作结果：返回v的(排在w之后的)下一个邻接顶点。 若w是v的最后一个邻接点，则返回“空”。,InsertArc(&G，v，

13、w)； 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中增添弧， 若G是无向的则还增添对称弧。 DeleteArc(&G，v，w)； 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除弧， 若G是无向的则还删除对称弧。,DFSTraverse (G，v，Visit()； 初始条件：图G存在，v是G中某个顶点， Visit是顶点的应用函数。 操作结果：从顶点v起深度优先遍历图G， 并对每个顶点调用函数Visit一次且仅一次。 BFSTraverse (G，v，Visit()； 初始条件：图G存在，v是G中某个顶点， Visit是顶点的应用函数。 操作结果：从顶点v起广度

14、优先遍历图G， 并对每个顶点调用函数Visit一次且仅一次。 ADT Graph,习题,试分别在邻接矩阵和邻接表表示的图上实现运算FirstAdjVex(G，v)和 NextAdjVex(G，v，w)； 试根据邻接矩阵建立图的邻接表表示。 画出下图的邻接表表示：,图的遍历,图的遍历：从某个结点出发，访问图的每个结点恰好一次。,1）访问v,访问v的邻接点w1,访问w1的邻接点w2, ,直至wm的邻接点全被访问过； 2）退回最近一个有未访问邻接点的wk, 重复1）直至所有与v连通的结点均被访问过。,深度优先从v开始遍历：,图的深度优先遍历,深度优先从v1开始遍历：,为了避免重复访问，设置一个标志顶

15、点是否被访问过的辅助数组 visited ： 它的初始状态为 0； 若顶点 i 被访问，则置 visited i 为 1，防止它被多次访问。,1）访问v； 2）依次深度优先从v的未被访问的邻接点遍历， 直至所有与v连通的结点均被访问过。,深度优先从v开始遍历：,void DFSTraverse(Graph G，Status(*Visit)(int v) /对图G作深度优先遍历。 VisitFunc=Visit; /使用全局变量VisitFunc，使DFS不必设函数指针参数 for(v=0；vG.vexnum；+v) visitedv=FALSE; /访问标志数组初始化 for(v=0；vG.v

16、exnum； +v) if( !visitedv ) DFS(G，v)； /对尚未访问的顶点调用DFS ,void DFS (Graph G，int v) /从第v个顶点出发递归地深度优先遍历图G。 visitedv=TRUE； VisitFunc(v)； /访问第v个顶点 for(w =FirstAdjVex(G, v); w=0; w =NextAdjVex(G, v, w) if(!visitedw) DFS(G，w)； /对v的尚未访问的邻接顶点w递归调用DFS ,算法分析,void DFS (Graph G，int v) /从第v个顶点出发递归地深度优先遍历图G。 visitedv=

17、TRUE； VisitFunc(v)； /访问第v个顶点 for(w =FirstAdjVex(G, v); w=0; w =NextAdjVex(G, v, w) if(!visitedw) DFS(G，w)； /对v的尚未访问的邻接顶点w递归调用DFS ,每个结点最多调用一次,每个结点一次,循环工作量： 寻找结点v的邻接点,时间复杂度： 访问每个结点的时间：O(n); 寻找每个结点的所有邻接结点工作量; 设图中有 n 个顶点，e 条边。 如果用邻接表表示图，沿 Firstedge link 链可以找到某个顶点 v 的所有邻接顶点 w。 无向图有 2e 个边结点，有向图有e个边，所以扫描边的

18、时间为O(e); 时间复杂度为O(n)+O(e)=O(n+e); 如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n)+O(n2 ) = O(n2).,广度优先遍历,基本思想 访问v1; 访问v1的邻接点w1,w2,wm; 依次访问w1, w2, 的未被访问的邻接点， 如此进行下去，直至访问完所有结点。,算法的实现需要 设置一个数组visited标记结点是否访问过； 设置一个队列纪录当前层访问的结点以备访问下一层结点。,取一个结点未访问结点v, 访问v，标记，入队； （访问 v的所有邻接点）：取队头元素，每次取v的下一个未访问的邻接点访

19、问，标记并入队； 重复2, 直至队列空； 如果图中仍然有未访问的结点，重复1， 直至所有结点均已标记为访问过。,基本思想 访问v1; 访问v1的邻接点w1,w2,wm; 依次访问w1, w2, 的未被访问的邻接点， 如此进行下去，直至访问完所有结点。,void BFSTraverse(Graph G，Status(*Visit)(int v) /按广度优先非递归遍历图G。 /使用辅助队列Q和访问标志数组visited。 for(v=0；vG.vexnum；+v) visitedv=FALSE； InitQueue(Q)； /置空的辅助队列Q,for(v=0； vG.vexnum； +v) if

20、(!visitedv ) /v尚未访问 visitedv=TRUE；visit(v)； EnQueue(Q，v)； /v入队列 while(!QueueEmpty(Q) DeQueue(Q，u) /队头元素出队并置为u for(w=FirstAdjVex(G,u); w; w=NextAdjVex(G, u, w) if(!Visitedw) /w为u的尚未访问的邻接顶点 visitedw=TRUE; Visit(w); EnQueue(Q,w); /if /while /if /BFSTraverse,复杂度与深度优先相同,图的连通性,对于连通的无向图，从一个结点出发可以访问所有结点；结点与

21、遍历时通过的边构成图的生成树；,深度优先生成树,广度优先生成树,对于不连通的无向图，则需从多个顶点出发访问；结点与遍历时经过的边构成生成树林。,深度优先生成森林,voidDFSTraverse(Graph G，Status(*visit)(int v) visitFunc=Visit; for(v=0；vG.vexnum；+v) visitedv=FALSE; for(v=0；vG.vexnum； +v) if( !visitedv ) DFS(G，v)； ,void DFS (Graph G，int v) visitedv=TRUE；VisitFunc(v)； for(w =FirstAdj

22、Vex(G,v); w=0; w =NextAdjVex(G, v, w) if(!visitedw) DFS(G，w)； ,每次循环 生成一棵树,void DFSForest (Graph G，CSTree /建立以p为根的生成树 /DFSForest,T,q,p,void DFSForest (Graph G，CSTree /建立以p为根的生成树 /DFSForest,T,q,p,第一次生成的树,上次生成的树,新生成的根结点,建立生成树,void DFSTree (Graph G，int v，CSTree *p=GetVex(G,w)，NULL，NULL； if (first) T-lch

23、ild=p； first=FALSE； else q-nextsibling =p； q = p； DFSTree(G, w, q)； /if /DFSTree,T,p,q,最小生成树,问题：设在n个城市间建立通信网络，要求建设费用尽可能低。,模型：n个结点的图，结点连线的权表示建设两点间通信线路的费用。在此网络的生成树中找出建设费用最小的生成树。,最小生成树,设G是一个带权的无向图（网络），则G的生成树可能有多个，生成树各边的权之和称为生成树的权。网络G的具有最小权的生成树称为G的最小生成树。,模型：n个结点的图，结点连线的权表示建设两点间通信线路的费用。求此网络的最小生成树。,应用：设在n

24、个城市间建立通信网络，要求建设费用尽可能低。,Prim算法,假设N=(V，E)是连通网，T=(U,TE)表示下列算法构造的N上最小生成树。 算法从U=u0(u0V)，TE= 开始; 重复执行下述操作, 直至U=V为止：在所有 uU，vV-U的边(u，v)E中找一条权最小的边(u，v)，将v并入U，同时边(u，v)并入集合TE。,设N有n个结点. 则算法结束时, T中必有n个结点, n-1条边. 在2中, 如果有相同权的边,可任选一条, 故最小生成树不唯一.,例: 求下图的最小生成树,初始状态: U=v0,循环: 对于每个结点viU，在vi与U中所有结点的邻接边中找出权最小的边ei=(vi,uk

25、), 并在这些边ei中求出权最小的边, 设为(vi, uk). 将uk并入U, (vi, uk)并入构造中的生成树。,MST性质,定理: 假设N=(V，E)是一个连通网, T=(U, TE)是正在构造的生成树, 若 (u，v)是一条端点分别在U和V-U,并具有最小权值的边，则必存在一棵包含T和边 (u，v)的最小生成树。,证明:用反证法.设任何包含T的最小生成树均不包含边e=(u,v).设T是一颗这样的树. 将e加到T中必然得到一条回路: u, w1, , wk,v, u 其中必然存在边e=(wp, wp+1), wpU, wp+1 U 去掉边e后打开回路, 又形成一颗生成树T, 因为W(e)

26、= W(e), 故T是一颗包含T和e的最小生成树. 矛盾!,Prim算法的实现,需要设置一个数组closedge, 纪录当前每个结点viU到达U的最小权边(vi, uk)的信息, 即closedegei为 (uk, minimumW(vi, uk)| uk U) struct VertexType adjvex； VRType lowcost； closedge MAX_VERTEX_NUM ,初始状态: U= v0 closedge0 = (v0 , 0); /0表示相应结点属于U closedgei = (v0, W(vi, v0),在closedge中选择最小权的边。假设vk U是clo

27、sedge中具有最小权边的结点, 则置 closedgeklowcost= 0, 即将vk并入 U 修改closedge: 对于vj U, 只需考虑可能出现的新边(vj, vk)是否具有更小的权 closedgej = min closedgej.lowcost, W (vj, vk),循环：,void MiniSpanTree_PRIM(MGraph G，VertexType u) /用普里姆算法从第u个顶点出发构造网G的最小生成树T， /输出T的各条边。假设用邻接矩阵存储G. k =LocateVex(G，u)； for(j=0； j0)边 printf(closedgek.adjvex,

28、 G.vexsk); /输出生成树的边 closedgek.lowcost=0; /第k个顶点并入U集 for(j=0; jG.vexnum; +j) if (G.acrskj.adjclosedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj; /for /MiniSpanTree,时间复杂度： O(n)+O(n2) = O(n2),Kruskal算法,假设连通网N=(V，E)，使用Kruskal构造最小生成树的算法： 最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，)，图中每个顶点自成一个连通分量 在E中选择代价最小且顶点落在T中不同的连通

29、分量上的边，将此边加入到T中； 重复上述过程2，直至所有顶点都在同一连通分量上为止。,克鲁斯卡尔算法构造最小生成树的过程,Kruskal算法可以用堆来实现。设e是图的边数， 则构造最小生成树的总时间代价是O(elog e).,可见，Prim算法适合于边数多的图， 而Kruskal算法适合于边数少(en2)的图。,拓扑排序,一个工程(project)可分为若干个称作活动(activity)的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。,计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则

30、不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8,这样的工程流程图可以用一个有向图表示：,结点表示活动， 有向边(u, v)表示u必须先于v完成。 这种图称为顶点表示活动的网（Activity on Vertices Nextwork），或者AOV网络.,AOV网是否存在有向环可以通过检查有向图是否存在一个拓扑排序，即将所有子工程排成线性序后所有的约束

31、条件均满足：如果(u,v)是边，则v必然排在u之后。,AOV活动能够顺利进行的条件是不存在有向环;,工程能否顺利进行呢?,上述AOV网的一个拓扑排序是： C1, C2, C3, C4, C5, C6, C8, C9, C7 如果一个学生每学期只能修一门课，则必须按照上述顺序进行。,拓扑序列： 对于有向无环图（Directed Acyclic Graphs DAG） G=（V，E），V里顶点的线性序列称作一个拓扑序列，如果该顶点序列满足： 若在有向无环图G中从顶点Vi到Vj有一条边，则在序列中顶点Vi必在顶点Vj之前。,如果AOV网络存在一个拓扑序列，则该AOV网络中必定不会出现有向环，拓扑序列

32、表示活动的一种顺序进行方式； 相反，如果不存在拓扑序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。,拓扑排序方法： (1)在有向图中选一个没有前驱的顶点输出； (2)从图中删除该顶点和所有以它为始点的边。 (3)重复上述两步，直至 全部顶点均已输出，排序完成； 当前图中不存在无前驱的顶点，则有向图中存在环。,v5,v6 - v1 - v4 - v3 - v2 - v5,如何在计算机中实现? 使用一个存放顶点入度的数组(indegree) ，入度为零的顶点即为没有前驱的顶点。 输出顶点及删除以它为始点的边的操作，则可以用终点的入度减1来实现。 采用邻接表作有向图的存储结构

33、。 为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。,使用这种栈的拓扑排序算法可以描述如下： (1) 初始化数组indegree; (2) 建立入度为零的顶点栈; (3) 当入度为零的顶点栈不空时, 重复执行 从顶点栈中退出一个顶点, 并输出之; 从AOV网络中找到从这个顶点发出的边, 边的终顶点入度减一; 如果边的终顶点入度减至0, 则该顶点进入度为零的顶点栈; (4) 如果输出顶点个数少于AOV网络的顶点个数, 则报告网络中存在有向环。,栈:,C4 C2,Status TopologicalSort(ALGraph G) /有向图G采用邻接表存储结构。若G无回路，则输出

34、/G的顶点的1个拓扑序列并返回OK，否则ERROR。 FindInDegree(G，indegree)； /对各顶点求入度indegree0vernum-1 InitStack(S)； for(i=0；iG.vexnum； +i) if(!indegreei) Push(S，i) /建零入度顶点栈,s入度为0者进栈 count=0； /对输出顶点计数,while (!StackEmpty(S) Pop(S，i)； printf(i，G.verticesi.data)； +count； /输出i号顶点并计数 for(p=G.verticesi.firstarc；p； p=p-nextarc) k

35、=p-adivex； /对i号顶点的每个邻接点的入度减1 if(！(-indegreek) Push(S，k)；/若入度减为0，则入栈 /for /while if(countG.vexnum) return ERROR；/该有向图有回路 else return OK； /TopologicalSort,复杂度分析,Status TopologicalSort(ALGraph G) /有向图G采用邻接表存储结构。若G无回路，则输出 /G的顶点的1个拓扑序列并返回OK，否则ERROR。 FindInDegree(G，indegree)； /对各顶点求入度indegree0vernum-1 Ini

36、tStack(S)； for(i=0；iG.vexnum； +i) if(!indegreei) Push(S，i) /建零入度顶点栈,s入度为0者进栈 count=0； /对输出顶点计数,O(e),O(n),while (!StackEmpty(S) Pop(S，i)； printf(i，G.verticesi.data)； +count； /输出i号顶点并计数 for(p=G.verticesi.firstarc；p； p=p-nextarc) k=p-adivex； /对i号顶点的每个邻接点的入度减1 if(！(-indegreek) Push(S，k)；/若入度减为0，则入栈 /for

37、 /while if(countG.vexnum) return ERROR；/该有向图有回路 else return OK； /TopologicalSort,循环次数: 结点i的出度,循环次数:n次, 因为每个结点入栈,出栈一次, 总数:,分析算法：对有n个顶点和e条弧的有向图而言， 建立求各顶点的入度的时间复杂度为O(e)； 建零入度顶点栈的时间复杂度为O(n)； 在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减1的操作在WHILE语句中总共执行e次，所以， 总的时间复杂度为O(n+e)。,用边表示活动的网络,在无有向环的带权有向图中 用有向边表示一个工程中的各项活动

38、(Activity) 用边上的权值表示活动的持续时间(Duration) 用顶点表示事件(Event) 则这样的有向图叫做用边表示活动的网络，简称AOE (Activity On Edges)网络。,事件v7： 活动a8,a9完成， a11可以开始,源点,汇点,关键路径,对AOE-网有待研究的问题是： (1)完成整项工程至少需要多少时间? (2)哪些活动是影响工程进度的关键?,事件8发生的条件 ： a10完成,并且 a11完成。,a11完成的时间： v7最早发生的时间+4,关键路径,事件8发生的时ve(8)： Maxve(6)+dut(a10), ve(7)+dut(a11),ve(4)： M

39、axve(1)+dut(), ve(2)+dut(),ve(i)：事件Vi 发生的最早可能时间 dut(a): 活动a需要的时间,ve(j)是从源点v0 到顶点vj 的最长路径长度，即vj最早的发生时间。 ve(j) = ve(i)+dut()| 是一个活动 j=1,2,n-1,从源点到汇点的最长路径叫做关键路径(Critical Path)。 关键路径上的活动称为关键活动，即关键活动是不按期完成会影响整个工程进度的活动。,汇点v(n-1)最早发生的时间是源点v0到汇点的最长路径长度。,对于一个事件vi, el(i)表示不影响整个工程进度前提下事件vi最迟发生的时间：,vl(6)+dut()

40、vl(8) =ve(8),vl(4)+dut() vl(6) vl(4)+dut() vl(7),vl(i) = vl(j)-dut()| 是一个活动 i=n-2, ,1,0,对于一个活动a=, e(a)=ve(i)是它最早可能开始的时间 l(a)=vl(j)-dut()是它最迟开始的时间 e(a)= l(a)的活动称为关键活动.,由此可以得到求AOE关键活动的算法. 求el(i), i = 1,2,n-1; 求ev(i), i = n-2,1,0; 对于每个活动a=, 如果e(a)=l(a),则a为关键活动.,计算ev数组,ve(j) = ve(i)+dut()| 是一个活动 j=1,2,n

41、-1 计算ve(j)需要先计算vj所有先驱结点最早发生时间.,方法: 在拓扑排序过程中计算ve. 1. 初始化ve: ve0vexnum-1 = 0; 2. 在排序中, 当结点i排序输出时, 修改i的每个直接后继结点j的最早发生时间vej: if (r = vei+dut() ) vej ) vej = r; 当j的所有前驱已经排序时,vej便是所求的值.,data firstarc,Status TopologicalOrder(ALGraph G，Stack /i号顶点入T栈并计数 for(p=G.verticesi.firstarc；p；p=p-nextarc) j=p-adjvex；

42、/对i号顶点的每个邻接点的入度减1 if(-indegreej=0) Push(S，j)； /若入度减为0，则入栈 if(vei+*(p-info)vej ) vej=vei+*(p-info)； /for *(p-info)=dut() /while if(countG.vexnum) return ERROR； /该有向网有回路 else return OK； /TopologicalOrder,求数组vl,vl(i) = vl(j)-dut()| 是一个活动 i=n-2, ,1,0,类似地, 计算vli需要先计算结点i的所有后继的vl值.,计算方法: 当逆拓扑序输出一个结点 j时, 修改

43、vlj: 对于 j的每个直接后继k, if (r=vlk-dut()vlj) vlj=r;,Status CriticalPath (ALGraph G) /G为有向网，输出G的各项关键活动。 if(!TopologicalOrder(G，T) return ERROR； /初始化顶点事件的最迟发生时间 vl0G.vexnum-1=veG.vexnum-1； /按拓扑逆序求各顶点的vl值 while(!StackEmpty(T) for(Pop(T,j),p=G.verticesj.firstarc；p；p=p-nextarc) k=p-adjvex； dut=*(p-info)； /dut

44、if(vlk-dutvlj) vlj=vlk-dut； /for,输出关键活动,for(j=0；jnextarc) k=p-adjvex； dut=*(p-info)； ee=vej；el=vlk-dut； tag = (ee=e1) ? * ： ； printf(j，k，dut，ee，el，tag)； /输出关键活动 /CriticalPath,在拓扑排序求vei和逆拓扑有序求vli时, 所需时间为O(n+e), 求各个活动的ek和lk时所需时间为O(e), 总时间复杂度仍然是O(n+e)。,最短路径,问题的提出：一位旅客要从A城到B城 他希望选择一条途中中转次数最少的路线； 他希望选择一条

45、途中所花时间最短的路线； 他希望选择一条途中费用最小的路线；,这些问题均是带权图上的最短路径问题。,边上的权表示一站 边上的权代表距离 边的权代表费用,设G是带权有向图， 称路径上的第一个顶点为源点(Source)，最后一个顶点为终点(Destination)； 一条路经的长度是路径上边的权之和； 最短路径问题：如果从图中某一顶点出发到达另一顶点的路径可能不止一条，如何找到一条长度最小的路径。,单源最短路径问题： 设G是带权(=0)有向图，给定一个顶点v， 求v到其余顶点的最短距离。,最短路径的Dijkstra算法,Dijkstra算法基本思想: 按路径长度的递增次序，逐步产生最短路径. 设源

46、点为v0 首先求出v0为源点长度最短的一条最短路径， 即具有最小权的边; 求出源点到各个顶点下一个最短路径：设其终点是u，则v0到u的最短路径或者是边，或者由一条已求得的最短路径（v0v)和边构成； 重复2直到从顶点v0到其它各顶点的最短路径全部求出为止。,例：求v0其他各点的最短路径 用S表示已求出最短路径的结点集初始状态：S=v0,第一条最短路径：( v0, v2) S = v0,v2,求下一条最短路径： 先求v0到其他顶点vi的只经过S结点的路径：,v0 -v1: v0-v3: (v0,v2,v3) 60 v0-v4: (v0,v4) 30 v0-v5: (v0,v5) 100,第二条最短路径： (v0,v4) ， S = v0,v2, v4,第一条最短路径：( v0, v2) S = v0,v2,求下一条最短路径： 先求v0到其他顶点vi的只经过S结点的路径：,v0 -v1: v0-v3: (v0,v2,v3) 60, (v0,v4,v3) 50