课件参考第五

1、图的术语G1G2有无ABABECDCD 结点或 顶点： 结点或 顶点：ABAB 有 无（弧）、弧尾或初始结或边点、弧头或终止结点ABA：G1 =（V1，A1） V1 = A,B,C,DA1 = <A,B>, <A,C>,<C,D>, <D,A>B 有 有：G2 =（V2，A2） V2 = A,B,C,D,EA2 = (A,B), (A,C),(B,D),(B,E), (C,E),(D,E)2ALDS图的术语G1G1的子图有有ABAAAABCDCCDCD无G2无G2的子图ABAABABABEEECDDCDCD3ALDS图的术语 路径：在无G=(V,

2、E)中由顶点v至v 的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至 v之间有路径存在 连通图：无图 G 的任意两点之间都是连通的，则称 G 是连通图。 连通分量：极大连通子图G无G的三个连通分量无ABABFGEFGEHIJIJHKLKLMMCDCD4ALDS无的连通性图的术语 路径：在有G=(V,E)中由顶点v经有至v 的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v 之间有路径存

3、在 强连通图：有图 G 的任意两点之间都是连通的，则称 G 是强连通图。 强连通分量：极大连通子图G的两个强连通分量有有GABABCDCD5ALDS有的连通性图的术语 生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。特点：在生成加一条边之后，必定会形成回路或环。GG的生成树无无ABABEEHHMMCDCD6ALDS图的术语完全 图：有 n(n-1)/2 条边的无。其中 n 是结点总数。其中 n 是结点总数。 有向完全图：有n(n-1)条边的有 边的，边的图称之为网络。 邻接点：无有结点的度，请注意同结点的出度和入度的结点的度数的区别。G1无有G2ABABEHMCDCD

4、7ALDS图的其它术语图的结构1、邻接矩阵和邻接矩阵（labeled adjacency matrix）无的有的邻接矩阵(设有有n 个结点，则用 n 行 n 列的矩阵A 表示)1、标识：分别用数字1、2 n 标识这些结点，如用1、2 标识结点A、B。XY2、查边：若 从结点X出发到结点 Y有一条有，即。查找结点 X和结点Y的标识数，设分别为i、j；并设 Ai,j分别为起始结点和到达结点的标识数。=1。注意： i、j3、写0 ： n 行 n 列的矩阵A 的其它矩阵元素全部冲0。注意： Ai,iA=0。出度: i行之和。入度: j列之和。B00表示成右图矩阵01D1000100000108CALD

5、S图的四种常用的形式：邻接矩阵和邻接矩阵（labeled adjacency matrix）、邻接表、十字链表、邻接多重表图的结构1、邻接矩阵和邻接矩阵（labeled adjacency matrix）（续）无设无的无的邻接矩阵具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该无；并且 Ai,j =注意： Ai,i1 , 如果i 至 j 有一条无；AI,j = 0如果 i 至 j 没有一条无=0。i结点的度: i行或i列之和。上三角矩阵或下三角矩阵。AB0110010011100010100101110表示成右图矩阵ECD9ALDS图的结构1、邻接矩阵和邻接矩阵（labeled adj

6、acency matrix）（续）有设有的邻接矩阵具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有。并且 Ai,j = a ， 如果i 至 j 有一条有且它的为a；Ai,j = 空或其它标 志，如果 i 至 j 没有一条有。aABabbb表示成右图矩阵bbaaabCDa任意两点之间是否有边方便，仅耗费O(1) 时间。优点：缺点：即使 << n2 条边，也需内存 n2 单元，太多; 仅读入边的初始数据并建立邻接矩阵10就耗费 O( n2 ) 时间，太长。ALDS图的结构2、邻接表（adjacency list）具有 n 个结点，则用结点表、设有或无表示该有或无。结点表：用数

7、组或单链表的形式存放所有的结点。如果结点数n已知，则采用数组形式，否则采用单链表的形式更好。（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。优点：内存 结点数 缺点：确定 i -> j 是否有边，最坏需耗费O(n) 时间。无同一条示两次空间浪费一倍。有寻找进入某结点的边，非常。结点表中的结点的表示： 用数组data:结点的数据场，保存结点的数据值。firstarc:结点的指针场，给出自该结点出发的的第一条边的边结点的地址。11ALDSdatafirstarc图的结构2、邻接表（adjacency list） 结点表中的结点的表示：续 用单链表data:结

8、点的数据场，保存结点的数据值。firstarc:结点的指针场，给出自该结点出发的的第一条边的边结点的地址。nextvex:结点的指针场，给出该结点的下一结点的地址。边结点表中的结点的表示：info:边结点的数据场，保存边的等。adjvex:边结点的指针场，给出本条边依附的另一结点（非出发结点）的地址。nextarc:结点的指针场，给出自该结点出发的的下一条边的12边结点的地址。ALDSinfoadjvexnextarcdatafirstarcnextvex图的结构2、邻接表（adjacency 实例：list）data firstarcadjvex nextvex1234G1AB!寻找进入结点

9、的边非常改进：建立逆邻接表或十字链表Adjvex 指针场之值为相应结点数的组元素的下标!CDG2无data firstarcAB12345adjvex nextvexECD六条边却用了 12 个边结点!改进：建立邻接多重表13ALDS4null325null25null15null41ABCDE3null21null4null3null2ABnullCD图的结构2、邻接表（adjacency 逆邻接表实例：list）G1有AB1234CD14ALDSGO263null1null1nullABCD3null4图的结构3、十字链表 结点表中的结点的表示：data:结点的数据场，保存结点的数据值。f

10、irstin: 结点的指针场，给出自该结点出发的的第一条边的边结点的地址。firstout:结点的指针场，给出进入该结点的第一条边的 边结点的地址。 边结点表中的结点的表示：info:边结点的数据场，保存边的等。tailvex:本条边的出发结点的地址。headvex:本条边的终止结点的地址。hlink:出发结点相同的边中的下一条边的地址。tlink:终止结点相同的边中的下一条边的地址。15ALDSinfotailvexheadvexhlinktlinkdatafirstinfirstout图的结构3、十字链表 实例：G1AB 用途：用于有，进入结点和离开结点的边容易。CDtailvex hea

11、dvex hlink tlinkA01BC23D16data firstin firstoutALDS32230231302001图的结构4、邻接多重表 结点表中的结点的表示：data:结点的数据场，保存结点的数据值。firstedge: 结点的指针场，给出自该结点出发的的第一条边的边结点的地址。 边结点表中的结点的表示：info: 边结点的数据场，保存边的等。mark:边结点的标志域，用于标识ivex: 本条边依附的一个结点的地址。ilink: 依附于该结点（地址由ivex给出）的边中的下一条边的的地址。该条边是否被过。jvex: 本条边依附的另一个结点的地址。jlink: 依附于该结点（地

12、址由jvex给出）的边中的下一条边的的地址。17ALDSmarkivexilinkjvexjlinkinfodatafirstedge图的结构4、邻接多重表 实例：A 用途：用于无，中 无G2B的边结点只需存放一次，节约内存。ECDmark ivexilink jvex jlinkdata firstedge212345A B1C35DE452518ALDS2413图的遍历1、深度优先搜索 注意：每个结点只能被一次，又因为一个结点可以和其它的任何结点相邻接，为了避免对一个结点的重复，必须对过的结点加以标记。结点的邻接结点的次序是任意的，因此深度优先搜索的序列可能有多种。深度优先搜索类似于树的前

13、序周游。方式：1、选中第一个被2、对结点作已的结点。过的标志。3、依次从结点的未被过的第一个、第二个、第三个 邻接结点出发，进行深度优先搜索。转向2。4、如果还有顶点未被5、所有的结点都被，则选中一个起始结点，转向2。到，则结束。19ALDS图的三种常见的遍历形式： 深度优先搜索 广度优先搜索 优先优先搜索图的遍历1、深度优先搜索:续有的实例：为了说明问题，邻接结点的次序以序号为准。序号小的先。如：结点 5 的邻接结点有两个 6、7，则先结点 6，再结点 7。621· 55· 6· 77431从结点出发的搜索序列：· 21、2、3、4没有搜索到所有的结点

14、，必· 1· 5· 3· 4· 6· 7须另选图中未访问过的结点，· 2从结点出发的搜索序列：5、6、2、3、1、4、75继续进行搜索。· 4· 1· 3适用的数据结构：栈20ALDS图的遍历1、深度优先搜索:续 搜索的实现。使用的变量说明：Boolean visitedMAX ;Status ( * VisitFunc) (int v);/用于标识结点是否已被/函数变量过时间复杂性： 邻接矩阵：O（n2） 邻接表O（n + e） n：结点数e：21ALDSvoid DFS( Graph G,

15、int v ); Visitedv = true; VisitFunc(v);for ( w = FirstAdjVex(G, v) ; w ; w = NextAdjVex(G, v, w) )if ( ! Visited w ) DFS(G, w )void DFSTraverse( Graph G, Status ( * VisitFunc) (int v); VisitFunc = Visit;for ( v=0; v <G.vexnum; +v ) visitedv = false; for ( v=0; v <G.vexnum; +v )if ( ! Visited v

16、 ) DFS(G, v )图的遍历2、广度（宽度）优先搜索 注意：每个结点只能被一次，又因为一个结点可以和其它的任何结点相邻接，为了避免对一个结点的重复，必须对过的结点加以标记。结点的邻接结点的次序是任意的，因此广度优先搜索的序列可能有多种。广度优先搜索类似于树的从根出发的按层次遍历。方式：1、选中第一个被2、对结点 V 作已的结点 V过的标志。3、结点 V 的未被过的第一个、第二个、第三个第 M个邻接结点 W1 、W2、W3 Wm ，且进行标记。4、依次结点 W1 、W2、W3 Wm的邻接结点，且进行标记。3、4二步反复进行。5、如果还有结点未被6、所有的结点都被，则选中一个起始结点，也标记

17、为V，转向2。到，则结束。22ALDS图的遍历2、广度（宽度）优先搜索: 树：A树的按层次进行的次序：A、B、C、D、E、F、G、H、I、J、K、L适用的数据结构：队列CDBEFGHIJKLA 队列的变化：1、结点A进队2、结点A出队、BCD，队空3、结点A的儿子结点进队4、结点B出队、5、结点B的儿子结点进队6、结点C出队、7、结点C的儿子结点进队···CDDEFGDEFGHALDS图的遍历2、广度（宽度）优先搜索: 无的实例：为了说明问题，邻接结点的次序以序号为准。序号小的先。如：结点 1 的邻接结点有三个 2、12、11，则先结点 2、11，再结点 12。&

18、#183;11·2·111211·122·6·7·10·336710·9次序：·4·5·84589图的广度优先的1、2、11、12、3、6、7、10、4、5、8、9适用的数据结构：队列24ALDS图的遍历2、广度优先搜索:续使用的变量说明：Boolean visitedMAX ;Status ( * VisitFunc) (int v);/用于标识结点是否已被/函数变量过时间复杂性： 邻接矩阵：O（n2） 邻接表O（n + e） n：结点数e：25ALDSvoid BFSTravers

19、e( Graph G, Status ( * VisitFunc) (int v); VisitFunc = Visit;for ( v=0; v <G.vexnum; +v ) visitedv = FALSE; InitQueue(Q);for ( v=0; v <G.vexnum; +v ) if ( ! Visited v ) Visited v = TRUE; Visit(v); EnQueue(Q,v); while (!EmptyQueue(Q) DeQueue(Q,u);for ( w = FirstAdjVex(G, u) ; w ; w = NextAdjVex

20、(G, u, w) ) if ( ! Visited w ) Visited v = TRUE; Visit(v); EnQueue(Q, w) ;图的连通性问题1、无的连通分量和生成树 连通：顶点v至v 之间有路径存在 连通图：无图 G 的任意两点之间都是连通的，则称 G 是连通图。 连通分量：极大连通子图G的三个连通分量F无G无ABABGEFGEHIJHKLIJMMKLCDCD26ALDS图的连通性问题1、无的连通分量和生成树:续 生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成加一条边之后，必定会形成回路或环。因为在生成树的任意两点之间，本来就是连通的，添

21、加一条边之后，形成了这两点之间的第二条通路。GG的生成树无无ABABEEHHMMCDCD 生成方法：进行深度为主的遍历或广度为主的遍历，得到深度优先生成成树。 生成森林：在进行深度为主的遍历或广度为主的遍历时，对于非连通图，将得到多棵深27广度优先生度优先生成广度优先生成树。称之为生成森林。GO33图的连通性问题1、无的连通分量和生成树:续 生成森林：在进行深度为主的遍历或广度为主的遍历时，对于非连通图，将得到多棵深度优先生成广度优先生成树。称之为生成森林。G无G的生成森林F无ABABGEFGEHIJHKLIJMMKLCDCD28ALDS图的连通性问题2、有的强连通分量的求法 强连通图：有图

22、G 的任意两点之间都是连通的，则称 G 是强连通图。 强连通分量：极大连通子图G的两个强连通分量有G有ABABCDCD29ALDS图的连通性问题2、有的强连通分量的求法：续 强连通分量的求法：1、对有G 进行深度为主的搜索，按照退出该结点的次序给结点进行编号。最先的结点（即所有邻接点都搜索完）的编号为1，其它结点的编号按次序逐次增大 1。2、将有造新的有G 的所有的有记为 Gr进行倒置，构3、根据步骤 1 对结点进行的编号，选取最大编号的结点。从该结点出发，在有Gr 上进行深度为主的遍历。如果没有到所有的结点，则从剩余的那些结点中选取编号最大的结点再进行深度为主的遍历。直至所有的结点都被到为止

23、。4、在最后得到的生成森林中的每一棵生成树，都是有G 的强连通分量顶点集。30ALDS在主程序中置：count = 0DFS（vextex v）; vextex w;1、mark v = visited2、for （ v 的邻接表中的每一个邻接结点 w ）3、 if （ mark w = unvisited ）; 4、 DFS（w）; count + ;finished v = count;图的连通性问题2、有 求法实例的强连通分量的求法：续第一步44A第三步A2323CBCBG有AB1D1D第二步4有Gr3第四步ABACDCB2DCD1G二棵生成树的结点是有的两个强连通分量的顶点集：A、C、

24、D及B31ALDS图的连通性问题2、有的强连通分量的求法：续 断言：有的强连通分量中的顶点和第二次搜索时得到的生成森林中的生成的结点精确对应。证明要点：相互直达的v、w; 肯定在同一生成树之中。不管是 G 还是 Gr,假定在 Gr 中的根为x在 Gr 中，存在着由 x 至 v 的路径，那么在 G 中存在一条由 v 至 x 路径。在 G 中，由于 x 序号大，而 v 序号小；所有存在着一条 x 至 v 的路径。x、v直达同理：在 Gr 中，存在着由x至 w 的路径，那么在G中存在一条由 w 至 x 路径。G中，由于x序号大，而 w 序号小；所有存在着一条x至w的路径。x、w直达所以，Gr 中的任

25、意二点 v、w 之间，相互可以直达。有GABACBG二棵生成树的结点是有的两个强连通分量的顶点集：A、C、D及B32CDDALDS图的连通性问题3、最小代价生成树（简称：最小生成树） 定义：生成 实例：的（代价）之和最小的树。左图的最小代价生成树1615234344325656 MST 性质：假设 G = V, E 是一条代价最小的的最小代价生成树。通图，U 是结点集合 V 的一个非空子集。若 ( u, v ) 是u 属于 U , v 属于 V - U，则必存在一棵包括边 ( u, v ) 在内33ALDS图的连通性问题3、最小代价生成树（简称：最小生成树） MST 性质：假设 G = V,

26、E 是一条代价最小的的最小代价生成树。通图，U 是结点集合 V 的一个非空子集。若 ( u, v ) 是u 属于 U , v 属于 V - U，则必存在一棵包括边 ( u, v ) 在内证明：假定存在一棵不包括边 ( u, v ) 在内的最小代价生成树，设其为 T。将边( u, v )添加到树 T ，则形成一条包含 ( u, v ) 的回路。因此，必定存在另一条边 ( u，v ) ，且 u 属于 U , v 属于 V - U。删去边 ( u，v ) ，得到另一棵生成树 T ; 因为边 ( u, v ) 的代价小于边 ( u，v) 的代价，所以新的生成树T 将是代价最小的树。和原假设。新的生成树

27、T是树的理由：连通且无回路。TUV-Uvuvu34ALDS图的连通性问题3、最小代价生成树（简称：最小生成树）时间复杂性：O（n2）数据结构：栈35ALDS Prim 算法Prim 算法的基本描述设 U：set of vertex, G: Graph, T: set of edges(mininum cost spanning tree; u, v : vertex; V: set of vertex; /初始时，V 包含所有结点T ； U 1 ;while ( U != V ) 设 ( u,v ) 是一条代价最小的边，并且 u 在 U 中，v 在 V - U中。T = T U ( u,v )

28、；U = U U v ;图的连通性问题3、最小代价生成树（简称：最小生成树） Prim 算法的实例1156115 552342346443232 65656最小代价生成树36ALDS图的连通性问题3、最小代价生成树（简称：最小生成树） Prim 算法数据结构：U111U5556661115 5552342345 5234646464323232 6图G数组：closedge 6 6图G数组：closedge 6 5656 6图G56012345012345注意：closedge 0 . Lowcost = 0closedge 2 . Lowcost = 0 表示结13点已在U中lowcost

29、表示最小距离adjvex 表示相应结点37lowcost adjvexlowcostadjvexGO560520506242060105000图的连通性问题3、最小代价生成树（简称：最小生成树）Kruscal 算法115651155 552342346443232 65656最小代价生成树38ALDS图的连通性问题3、最小代价生成树（简称：最小生成树）Kruskal 算法的实现Kruscal 算法的基本描述设 U：set of vertex, G: Graph, T: minimum cost spanning tree ;u, v : vertex; V: set of vertex; E：

30、set of edges /初始时，V 包含所有结点T V , ; / T 初始时具有 n 个不同的连通分量，每个分量只有一个结点。T 的 n - 1 吗？等则结束在 E 中选择代价最小的边，如果 ( u,v ) 不和 T 中已有的边( u,v ) 。并置 E E ( u,v )。回路，则 T T ( u,v )，否则放弃。转回数据结构：优先队列（用堆实现）时间复杂性：O（eloge）39ALDS图的连通性问题3、最小代价生成树（简称：最小生成树）实例的执行过程15615 52346432 656图G151552344325640最小代价生成树ALDS1、初始连通分量：1,2,3,4,5,62

31、、反复执行添加、放弃动作。条件：不等于 n-1时边动作连通分量(1,3)添加1,3,4,5,6,2(4,6)添加1,3,4, 6,2,5(2,5)添加1,3,4, 6,2,5(3,6)添加1,3,4, 6,2,5(1,4)放弃因回路(3,4)放弃因回路(2,3)添加1,3,4,5,6,2有图及其应用1、何为有图（DAG 图）实例BBBEFGEFGEFGLFGLFGLFG有DAG图有（含环）用途：描述工程项目或系统进行的工具AOV 网络：定义结点为活动，有的指向表示活动执行的次序。AAOE网络：定义结点为刻）。有B，有的指向表示的执行次序。是时间（时定义为活动，它的10B定义为活动进行所需要的时

32、间。A41ALDS有图及其应用2、拓扑排序（Topological Sort） 偏序：若集合 X 上的关系 R 是传递的、自反的、关系。称的，则称 R 是集合 X 上的偏序全序：若关系 R 是集合 X 上的偏序关系，如果对于每个x, y 属于 X，必有 x R y 或y R x ，则称 R 是集合 X 上的全序关系。拓扑排序：如果有一个序列A = a1,a2,a3an 是集合 X 上的元素的一个序列， 且当 i < j 时， （ai , aj ）属于 R ，则称 A 是相对于 R 拓扑排序的。注意：且当表示（ai , aj ）属于 R， i < j 同时存在i 和 j 是元素 ai

33、 和 aj 在序列 A 中的序号。表示（ai , aj ）属于 R， i < j用aiajaiaj为了表示的方便，令为前件，而为后件。前件的序号一定要小于后件。否则将不满足拓扑排序的定义。用途：描述工程项目或系统进行的次序AOV 网络：定义结点为活动，有42的指向表示活动执行的次序。ALDS有图及其应用2、拓扑排序（Topological Sort） 实例：下述集合 M 代表课程的集合，其中，1代表数学， 2代表程序设计，3代表离散数学，4代表汇编程序设计，5代表数据结构，6代表结构程序设计, 7代表编译原理。关系 R 课程学习的先的先后次序表。，如数学必须在离散数学之前学习。要求排一张

34、学习132754643ALDS第一个输出的结点（序列中的第一个元素）：必须无前件后件：必须等到它的前件输出之后，因此时序号才会大于前 件的序号。无前件及后件的结点：任何时候都可输出。序列：1、3、2、4、6、5、7 合乎拓扑排序的要求序号 1、2、3、4、5、6、7 前件的序号 > 后件的序号序列：3、1、2、4、6、5、7 不合乎拓扑排序的要求序号 1、2、3、4、5、6、7元素 3 的序号 1（后件）< 元素 1 （前件） 的序号 2元素 3 的序号 1（后件）< 元素 2 （前件） 的序号 3有图及其应用2、拓扑排序（Topological Sort） 实例：下述集合

35、M 代表课程的集合，其中，1代表数学， 2代表程序设计，3代表离散数学，4代表汇编程序设计，5代表数据结构，6代表结构程序设计, 7代表编译原理。关系 R 课程学习的先的先后次序表。，如数学必须在离散数学之前学习。要求排一张学习546132465744ALDS有图及其应用2、拓扑排序（Topological Sort） 算法（使用邻接矩阵）：12345011000060100000700101101234567000000000000000000000010000001100000100000001011000000000000000000010000045ALDS算法的执行步骤：1、找到的第

36、 j 列，输出 j2、将第 j 行的全部元素置为零3、找到的第 k 列，输出 k4、将第 k 行的全部元素置为零反复执行 3、4；直至所有元素输出完毕。有图及其应用2、拓扑排序（Topological Sort）1 算法（使用邻接表）：327546栈indegree0123456012345646ALDS算法的执行步骤：1、用一个数组每个结点的入度。将入度为零的结点进栈。2、将栈中入度为零的结点V输出。3、根据邻接表找到结点V的所有的邻接结点，并将这些邻接结点的入度减一。如果某一结点的入度变为零，则进栈。4、反复执行 2、3；直至栈空为止。次序执行结束，如果输出结点数等于图的结点总数，则有 有

37、环，否则有 有环。6null6null6null45null431234null567null2null011121301有图及其应用2、拓扑排序（Topological Sort） 算法（使用邻接表）的程序：132754647ALDSStatus Topologicalsort（ ALGraph G） findinDegree（G，indegree）; Initstack（S）； for （i = 0; i < G.vexnum; +i）if （! Indegree i ）Push（S，i）; count = 0;while （！StackEmpty（S） Pop（S，i）; Prin

38、tf（i，vertices i .data）; +count; for （p=G.verticesi. firstarc; p; p=p->nextarc）; k = p->adjnexr;if （!（- - indegree k ） Push（S, k）; if （count < G.vexnum）return ERROR; else return OK; / end有图及其应用3、关键路径用途：估算工程项目完成时间AOE网络：定义结点为刻）。有术语：，有的指向表示的执行次序。是时间（时定义为活动，它的定义为活动进行所需要的时间。源点：表示整个工程的开始点，也称起点。收点：

39、表示整个工程的结束点，也称汇点。结点：活动（有时间，表示的是时刻。）：它的定义为活动进行所需要的时间。方向表示起始结点先10发生，而终止结点材能发生。AB最早能够的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味着发生的时刻。生时间（V l (j)）：不影响工程的如期完工，本结点刻。dut(j,k)的最必须发发生的时活动的最早开始时间：e( ai ) = Ve( j )jkai活动的最迟开始时间：l( ai ) = V l( k ) - dut( j , k )48ALDS有图及其应用3、关键路径术语：的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味着最早能够10发生

40、的时刻。AB生时间（V l (j)）：不影响工程的如期完工，本结点刻。dut(j,k)的最必须发发生的时jk活动的最早开始时间：e(ai ) = Ve( j )ai活动的最迟开始时间： l (ai ) = V l( k ) - dut( j , k )关键活动：最早开始时间 最迟开始时间的活动关键路径：从源点到收点的最长的一条路径，或者全部由关键活动的路径。12收点10起点:051288437VjVnV1VJ10Vl(Vj) = 取 10-2、10-4、10-3、10-7的最小值 3;或 10 - 最长路径 7Ve(Vj) = 88 取 1、5、12、88的最大值 8849ALDS有图及其应用

41、3、关键路径Ve(j) 及 Vl(j)）的求法：32起点:收点1051288437VjVn0V1VJ10Vl(Vj) = 取 10-2、10-4、10-3、10-7的最小值 3Ve(Vj) = 3、5、12、88的最大值 882Vu3Vv9Vw82Vx由源点至收点由收点至源点9Vu8Vv8Vw5Vx112123收点10VjVnV1VJ106250Ve(Vj) = Vj 的起始结点的最早发生时间 + 各Vl(Vj) = 取终止结点的最生时间中的和的最大值 88- 各自的边的的差的最小值 3自的边的ALDS有图及其应用3、关键路径实例：求0结点的最早发生时间0V522V6V2利用拓扑排序算法求间的

42、执行步骤：结点的最早发生时1100035V11、设每个结点的最早发生时间为0，将入度为零的结点进栈。2、将栈中入度为零的结点V取出，并压入另一栈，用于形成逆向拓扑排序的序列。3、根据邻接表找到结点V的所有的邻接结点，将结点V的最早发生时间 + 活动的 得到的和同邻接结点的早发生时间进行 V310V43、6V5V21比较；如果该值大，则用该值取代早发3、35、7、80V1生时间。另外，将这些邻接结点的入度减一。如果某一结点的入度变为零，则进栈。4、反复执行 2、3；直至栈空为止。V3V62V45、5正向拓扑排序：V151V2V3V4V5V6ALDS有图及其应用3、关键路径求0的最早发生时间的程序实现0V52V211000352V1V310V4V63、6V5V210V15、7、83、3V3V62V45、5正向拓扑排序：52V1V2V3V4V5V6ALDSStatus Topologicalsort（ ALGraph G, Stack &T） FindinDegree（G，indegree）;/ 对各顶点求入度，建立入度为零的栈S，Initstack（T