第七章 图 1、图的基本概念 2、图的存储表示 3、图的遍历与连通性 4、最小代价生成树 5、最短路径问题 6、AOV网络和AOE网络.

Presentation on theme: "第七章 图 1、图的基本概念 2、图的存储表示 3、图的遍历与连通性 4、最小代价生成树 5、最短路径问题 6、AOV网络和AOE网络."— Presentation transcript:

1 第七章 图 1、图的基本概念 2、图的存储表示 3、图的遍历与连通性 4、最小代价生成树 5、最短路径问题 6、AOV网络和AOE网络

2 图的基本概念 有向图 G1 无向图 G2 A B A B E C D C D 结点或 顶点： A B 结点或 顶点： A B
有向边（弧）、弧尾或初始结点、弧头或终止结点 无向边或边 A B A B 有向图：G1 =（V1，{A1}） V1 = {A,B,C,D} A1 = {<A,B>, <A,C>, <C,D>, <D,A>} 无向图：G2 =（V2，{A2}） V2 = {A,B,C,D,E} A2 = {(A,B), (A,C), (B,D), (B,E), (C,E), (D,E)}

3 图的基本概念 有向图 G1 有向图G1的子图 A B A A B A B C D C C D C D 无向图 G2 无向图G2的子图 A B
E E E C D D C D C D

4 无向图的连通性 路径：在无向图G=(V,{E})中由顶点v至v‘’ 的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。
简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v‘’ 之间有路径存在 连通图：无向图 G 的任意两点之间都是连通的，则称 G 是连通图。 连通分量：极大连通子图 无向图G 无向图G的三个连通分量 A B A B F G E F G E H I J I J H K L K L M M C D C D

5 有向图的连通性 路径：在有向图G=(V,{E})中由顶点v经有向边至v‘’ 的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。
简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v‘’ 之间有路径存在 强连通图：有向图图 G 的任意两点之间都是连通的，则称 G 是强连通图。 强连通分量：极大连通子图 有向图G 有向图G的两个强连通分量 A B A B C D C D

6 生成树 生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添 加一条边之后，必定会形成回路或环。 无向图G
A B A B E E H H M M C D C D

7 图的其它术语 n n 2 2 完全图：有 n(n-1)/2 条边的无向图。其中 n 是结点个数。
边的权值，边有权的图称之为网络。 邻接点： 无向图结点的度( 注意：同树中的结点的度定义是不同的 ) 有向图结点的出度和入度 2 n 2 n 无向图G1 有向图G2 A B A B E H M C D C D

8 图的ADT Data: 顶点和边的集合。边是连接一对顶点(v,u) 或 <v,u>的，其中(v,u) 是连接顶点v和u的无向
另一个顶点的代价。 Operations: Constructor 前提：无。 结果：创建一个包含顶点和边的集合的图。 Getweight 前提：顶点 Vi 和 Vj 组成的顶点对的数据值，该顶点对必须属于该图。 结果：如果顶点 Vi 和 Vj 之间的边如果存在，则返回其权值。 GetNeighbor 前提：顶点 V。 结果：返回和顶点相邻接的所有的顶点。 InsertVertex 前提：一个新的顶点。 结果：将该新顶点插入到图的顶点集合。 InsertEdge 前提：一条边的顶点 V 和 U 及其它们的权值，且顶点 V 和 U已在图中 ，而顶点 V 到 U 的边不在图中。 结果：将该条边插入到图中，图的边的集合的规模增大1。 RemoveVertex 前提：顶点 V 的数据值，并且它必须存在于图的顶点集之中。 结果：将该顶点删除，并且删除从顶点 V 出发的，和进入顶点 V 的所 有的边。图的边的集合和顶点的集合规模被更新。 RemoveEdge 前提：一条边的顶点 V 和 U 及其它们的权值，且相应的权值必须存在 于顶点的值的集合之中。 结果：如果该条边存在，则将它从图中删除，图的边的少1。

9 图的存储表示 图的四种常用的存储形式： 邻接矩阵和加权邻接矩阵（labeled adjacency matrix） 邻接表 十字链表
邻接多重表

10 邻接矩阵 0 1 2 3 1 2 3 0 1 2 3 A B C D 无权值的有向图的邻接矩阵
设有向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该有向图； 并且 A[i,j] = 1 , 如果i 至 j 有一条有向边；A[i,j] = 0如果 i 至 j 没有一条有向边 注意： A[i,i] = 0。出度: i行之和。入度: j列之和。 A B 1 2 3 表示成右图矩阵 C D 在物理实现时的考虑：分别用 0、1、2、3 分别标识结点A、B、C、D。而将真正的数据场之值放入一个一维数组之中。 A B C D

11 邻接矩阵 无权值的无向图的邻接矩阵 设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图；
并且 A[i,j] = 1 , 如果i 至 j 有一条无向边；A[i,j] = 0如果 i 至 j 没有一条无向边 注意： A[i,i] = 0。i结点的度: i行或i列之和。上三角矩阵或下三角矩阵。 A B 表示成右图矩阵 E C D 在物理实现时的考虑，和前一页的无向图类似。

12 加权邻接矩阵 有向图的加权邻接矩阵 设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图；
并且 A[i,j] = a , 如果i 至 j 有一条有向边且它的权值为a。A[i,j] = ‘ 空 或其它标 志；如果 i 至 j 没有一条有向边。 a A B a b b a a 表示成右图矩阵 b b a b C D a 优点：判断任意两点之间是否有边方便，仅耗费 O(1) 时间。 缺点：即使 << n2 条边，也需内存 n2 单元，太多; 仅读入数据耗费 O( n2 ) 时间，太长。

13 邻接表 邻接表（adjacency list） 设有向图或无向图具有 n 个结点，则用 结点表、边表表示该有向图或无向图。
组形式，否则应采用单链表的形式。!!! 提倡采用动态链表形式。 边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成 它的边结点单链表。 优点：存储量 ＝ 结点数 ＋ 边数 缺点：确定 i --> j 是否有边，最坏需耗费 O(n) 时间。无向图同一条边表示两次 边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。 结点表中的结点的表示： 用数组 data:结点的数据场，保存结点的数据值。 adj: 结点的指针场，给出自该结点出发的 的第一条边的边结点的地址。 data adj

14 邻接表 结点表中的结点的表示： 用单链表 data firstarc nextvex 边结点表中的结点的表示： cost dest link
数据值。 firstarc:结点的指针场，给出自该 结点出发的的第一条边的 边结点的地址。 nextvex:结点的指针场，给出该结 点的下一结点的地址。 结点表中的结点的表示： 用单链表 data firstarc nextvex 边结点表中的结点的表示： cost:边结点的数据场，保存边的 权值等。 dest:边结点的指针场，给出本 条边依附的另一结点（非 出发结点）的地址。 link: 结点的指针场，给出自该 结点出发的的下一条边的 边结点的地址。 cost dest link

15 邻接表 01234 实例： data adj dest link 向图 G1 0123 A 1 2 A B B C 3
null A B B null C 3 寻找进入结点的边非常困难!!! 改进：建立逆邻接表或十字链表 null D null C D 无向图 G2 data adj A B 1 2 01234 A null dest link B 3 4 null C E 4 null D 1 4 null E 2 3 1 C D null 6条边却用了 12 个边结点!!! 改进：建立邻接多重表

16 邻接表 0123 逆邻接表实例： 有向图 G1 A B 2 3 A B C D 2 C D
null B null C null D 2 null C D 注意：在说明邻接表表示图时，我们用数组表示了结点表，这是用于讲解原理用的。 但课本中采用用链表表示结点表。如下图所示，其中，<C> 为数据场之值为C的结点的地址，其余类推。 head A <C> <D> null B <A> null C <A> null D <C> null null

17 邻接表 邻接表的表示和实现： 向图 G1 A B C D 结点表 边表 head tag data next adj dest link A
C D 结点表 边表 head tag data next adj dest link A <B> <C> ∧ B ∧ C <D> ∧ D ∧ ∧ <A>

18 邻接表的实现 template <class VertexType, class EdgeType >
Graph< VertexType, EdgeType > :: Graph( VertexType flag, EdgeType tag):Vertex_finish_flag(flag),Edge_finish_flag(tag) { NumVertex = 0; NumEdge = 0; VertexType v, u; EdgeType e; Vertex<VertexType,EdgeType> * p,*q; // 指向顶点的指针。 cout << " Input vertex data one by one! " << endl; head = NULL; while ( cin >> v, v != Vertex_finish_flag ) { head = new Vertex<VertexType,EdgeType>( v, head, NULL ); Exception( !head, “Head is NULL!” ); NumVertex ++; }

19 邻接表的实现 cout << " Input edges data one by one! " << endl;
while ( cin >> v, cin >> u, cin >> e, e != Edge_finish_flag ) {   Exception( !(p = GetVertexPos(v)), “It is NULL!”); // 寻找边的出发顶点的地址，为空则错。 Exception (!( q = GetVertexPos(u)), “It is NULL!”); // 寻找边的到达顶点的地址，为空则错。 p->adj = new Edge<VertexType,EdgeType>( q, e, p->adj ); Exception( !p->adj, “ Fail on memory! ” ); NumEdge ++; }

20 十字接表 结点表中的结点的表示： data firstin firstout 边结点表中的结点的表示： mark ver1 ver2
数据值。 firstout: 结点的指针场，给出自该 结点出发的的第一条边的 边结点的地址。 firstin:结点的指针场，给出进入该 结点的第一条边的 边结点的地 址。 结点表中的结点的表示： data firstin firstout 边结点表中的结点的表示： mark:边结点的标志域 。本书未使用。 mark ver1 ver2 path2 Path1 ver1: 本条边的出发结点 的地址。 ver2: 本条边的终止结点 path1:出发结点相同的边 中的下一条边的地址。 path2:终止结点相同的边

21 十字接表 向图 G1 A B 用途：用于有向图， 查询 进入结点和离开结点 的边容易。 实例： C D ver1 ver2 path2
1 2 ∧ A 1 2 3 B ∧ C ∧ 2 2 3 ∧ D 3 ∧ 3 1 ∧ 3 2 ∧ ∧ data firstin firstout

22 邻接多重表 结点表中的结点的表示： data first 边结点表中的结点的表示： mark vertex1 path1 vertex2
数据值。 first: 结点的指针场，给出自该 结点出发的的第一条边的 边结点的地址。 结点表中的结点的表示： data first 边结点表中的结点的表示： info: 边结点的数据场，保存边的 权值等。本书未使用。 mark:边结点的标志域，用于标识 该条边是否被访问过。 mark vertex1 path1 vertex2 path2 info vertex1: 本条边依附一个结点的地址。 path1: 依附于该结点（地址由vertex1给出）的 边中的下一条边的的地址。 vertex2: 本条边依附的另一个结点的地址。 path2: 依附于该结点（地址由vertex2给出）的 边中的下一条边的的地址。

23 邻接多重表 01234 用途：用于无向图，边表中 的边结点只需存放一 次，节约内存。 实例： 无向图 G2 A B E
注意：本书介绍的图的存储表示方法， 计有：邻接矩阵、邻接表、逆邻接 表、十字链表、邻接多重表。除邻 接矩阵之外，其它几种表示方法中 的结点表和边表，都应该采用动态 链表表示。因为这将避免顺序存储 的许多缺点。 C D mark data first 1 01234 A ∧ 2 ∧ B C 2 4 1 ∧ 3 ∧ D E 4 1 3 4 ∧ vertex1 path1 vertex2 path2

24 图的遍历与连通性 图的三种常见的遍历形式： 深度优先搜索 广度(或宽度)优先搜索 优先度优先搜索

25 深度优先搜索 注意：每个结点只能被访问一次，又因为一个结点可以和其它的任何结点相邻接，
为了避免对一个结点的重复访问，必须对访问过的结点加以标记。 结点的邻接结点的次序是任意的，因此深度优先搜索的序列可能有多种。 深度优先搜索类似于树的前序周游。 访问方式：1、选中第一个被访问的结点。 2、对结点作已访问过的标志。 3、依次从结点的未被访问过的第一个、第二个、第三个…… 邻接结 点出发，进行深度优先搜索。转向2。 4、如果还有顶点未被访问，则选中一个起始结点，转向2。 5、所有的结点都被访问到，则结束。

26 深度优先搜索 有向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：
结点 5 的邻接结点有两个 6、7，则先访问结点 6，再访问结点 7。 6 2 1 5 5 6 7 7 4 3 从结点 出发的搜索序列： 1、2、3、4没有搜索 到所有的结点，必 须另选图中未访 问过的结点， 继续进行 搜索。 1 2 1 5 3 4 6 7 2 从结点 出发的搜索序列： 5、6、2、3、1、4、7 适用的数据结构：栈 5 4 1 3 声明：深度（或广度）优先生成树应遵守规范的画法。

27 深度优先搜索的实现 #include "SqStack.h"
template <class VertexType, class EdgeType > void Graph< VertexType, EdgeType > :: DFS_Traveling( const VertexType & start ) { Stack< Edge<VertexType,EdgeType> * > s(NumEdge); Vertex<VertexType,EdgeType> * p, *m; Edge<VertexType,EdgeType> * q; p = head; while ( p ) { p->tag = 0; p = p->next; } // 置所有顶点未被访问过的标志。 p = GetVertexPos( start ); // 得到 DFS 遍历的起始顶点。 if ( !p ) { cout << " Start vertex is Error ! " << endl; return ; } int finished =0;

28 深度优先搜索的实现 while( p ) { if ( p->tag = = 0 )
cout << "visited vertex data:" << p->data << endl; // 访问顶点。 if ( p->adj ) s.Push( p->adj ); while( !s.IsEmpty( ) ) { q = s.Top( ); s.Pop( ); if ( q->link ) s.Push( q->link ); m = q->dest; if ( m->tag = = 0 ) { m->tag = 1; // 设置已被访问的标志。 cout << "visited vertex data:" << m->data << endl; //访问 if ( m->adj ) s.Push( m->adj ); } p = p->next; if ( !p && !finished ) { p= head; finished =1; } return; 时间复杂性： 邻接矩阵：O（n2） 邻接表： O（n + e） n：结点数 e：边数

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

30 广度优先搜索 树： A 树的按层次进行访问的次序： A、B、C、D、E、F、G、H、 I、J、K、L 适用的数据结构：队列 C D B E
队列的变化： B C D 1、结点A访问后进队 2、结点A出队、队空 3、结点A的儿子结点B、C、D访问后进队 4、结点B出队 5、结点B的儿子结点E、F、G访问后进队 6、结点C出队 7、结点C的儿子结点H访问后进队 C D C D E F G D E F G D E F G H

31 广度优先搜索 · · · · · · · · · · · · 无向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：
结点 1 的邻接结点有三个 2、12、11，则先访问结点 2、11，再访问结点 12。 1 1 12 11 11 2 2 12 3 6 7 10 3 6 7 10 4 5 8 9 4 5 8 9 图的广度优先的访问次序： 1、2、11、12、3、6、7、10、4、5、8、9 适用的数据结构：队列 注意：结点被访问后，进队；然后队首结点出队….. 时间复杂性： 邻接矩阵：O（n2） 邻接表： O（n + e） n：结点数 e：边数

32 无向图的连通分量和生成树 连通：顶点v至v‘’ 之间有路径存在 连通图：无向图图 G 的任意两点之间都是连通的，则称 G 是连通图。
连通分量：极大连通子图 无向图G的三个连通分量 无向图G A B A B F G E F G E H I J H K L I J M M K L C D C D

33 无向图的连通分量和生成树 生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添 加一条边之后，必定会形成回路或环。因为在生成树的任意两点之间，本来就 是连通的，添加一条变之后，形成了这两点之间的第二条通路。 无向图G 无向图G的生成树 A B A B E E H H M M C D C D 生成方法：进行深度为主的遍历或广度为主的遍历，得到深度优先生成树或广度优先生 成树。 GO38

34 无向图的连通分量和生成树 生成森林：在进行深度为主的遍历或广度为主的遍历时，对于非连通图，将得到多棵深
度优先生成树或广度优先生成树。称之为生成森林。 无向图G 无向图G的生成森林 A B A B F G E F G E H I J H K L I J M M K L C D C D 图的优先度优先搜索(Priority First Search )：根据优先度确定首先被访问的邻接顶点。 如：最小生成树中的 Prim 算法等。

35 有向图的强连通分量的求法 强连通图：有向图图 G 的任意两点之间都是连通的，则称 G 是强连通图。 强连通分量：极大连通子图 有向图G
A B A B C D C D

36 有向图的强连通分量的求法 在主程序中置：count = 0 DFS（vextex v）; { vextex w;
1、mark [ v ] = visited 2、for （ v 的邻接表中的每一个邻接结 点 w ） 3、{ if （ mark [ w ] == unvisited ）; 4、 DFS（w）; } count ++ ; finished [ v ] = count; } 1、对有向图 G 进行深度为主的搜索，按照退 出该结点的次序给结点进行编号。最先退 出的结点的编号为 1，其它结点的编号按 次序逐次增大 1。 2、将有向图 G 的所有的有向边进行倒置，构 造新的有向图记为 Gr 3、根据步骤 1 对结点进行的编号，选取最大 编号的结点。从该结点出发，在有向图 Gr 上进行深度为主的遍历。如果没有访问 到所有的结点，则从剩余的那些结点中 选取编号最大的结点再进行深度为主的遍 历。直至所有的结点都被访问到为止。 4、在最后得到的生成森林中的每一棵生成树 ，都是有向图 G 的强连通分量顶点集。

37 有向图的强连通分量的求法 实例： 第一步 A 第三步 A 有向图G C B C B A B D D 第二步 有向图Gr A B 第四步 A
注意：在第 3 步中，在Gr选取序号最大的结点开始进行 DFS，目的是保证以该结点为根得到的生成树中，其它结点的序号都比它小。这在 G 的相应的生成树中，由根到其它结点之间，是有路径，即连通的。 实例： 第一步 4 A 第三步 4 A 有向图G 2 C 3 B 2 C 3 B A B 1 D 1 D 第二步 有向图Gr 3 4 A B 第四步 A C D C B 2 D C D 1 二棵生成树的结点是有向图G的两个强连通分量的顶点集：{A、C、D}及{B}

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

39 最小生成树 GO32 定义：生成树中边的权值（代价）之和最小的树。 实例： 左图的最小代价生成树 V0 V0 V1 V2 V3 V1 V2
5 6 1 1 V1 5 V2 5 V3 V1 5 V2 V3 6 4 4 3 2 3 2 V4 6 V5 V4 V5 GO32

40 例：Kruscal 算法 V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树 5 6 5 1 1 5 5

41 例： Kruscal 算法 实例的执行过程 1、初始连通分量： {0},{1},{2},{3},{4},{5}
2、反复执行添加、放弃动作。条件：边数不等于 n-1时 边 动作 连通分量 (0,2) 添加 {0,2},{1},{3},{4},{5} (3,5) 添加 {0,2},{3, 5},{1},{4} (1,4) 添加 {0,2},{3, 5},{1,4} (2,5) 添加 {0,2,3,5},{1,4} (0,3) 放弃 因构成回路 (2,3) 放弃 因构成回路 (1,2) 添加 {0,2,3,5,1,4} V0 5 6 1 V1 5 V2 5 V3 6 4 3 2 V4 6 V5 图G V0 5 1 5 V1 5 V2 V3 4 3 2 V4 V5 算法实现要点: 每个结点增加一个数据场，用于标识该结点所属的集合。可用于判断新的边加入后是否构成回路。 最小代价生成树

42 Kruscal 算法 设 U：set of vertex, G: Graph, T: mininum cost spanning tree ; u, v : vertex; V: set of vertex; E：set of edges //初始时，V 包含所有结点 { T ＝ { V , φ }; // T 初始时具有 n 个不同的连通分量，每个分量只有一个结点。 T 的边数 ＝ n - 1 吗？等则结束 在 E 中选择代价最小的边，令为 ( u,v ) 。并置 E ＝ E － ( u,v )。 如果 ( u,v ) 不和 T 中已有的边构成回路，则 T ＝ T ∪ ( u,v )，否则放弃。转回 } 数据结构：用邻接表表示图，用最小化堆实现挑选代价最小的边。 时间复杂性级别：O(eloge)，用于稀疏图。如：边数 e 和顶点数 n 成正比。

43 最小生成树 MST 性质：假设 G = {V, { 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 ‘ 将是代价最小的树。和原假设矛盾。 T v u v’’ u’’

44 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 ＝ { v0 }; // T为最小生成树的边集合 由于v0在 U 中，其余各结点都在 V－U 中，可用一数组记录 V－U中的结点至v 的路径。因为它们构成了当前横跨 U 和 V－U 两个集合的所有的边。 while ( U != V ) { 设 ( u,v ) 是一条代价最小的边，并且 u 在 U 中，v 在 V - U中。 T = T + ( u,v )；U = U + { v }; 由于 v 已被加入U 中，查找 由 v 至它的仍在 V－U中的邻接结点w的边 ，若小于原来相应的数组元素记录的最小值，则数组元素之值用该值取 代。即：该值为从w（在V-U中）到U中的所有边中最短的一条边的长度 }

45 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6

46 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6
  最小代价生成树的生成过程

47 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6
  最小代价生成树的生成过程

48 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6

49 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6

50 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6

51 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6

52 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6

53 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6

54 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 5 1 6

55 例：Prim算法 U V0 V0 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 最小代价生成树的生成过程 5 6 1 1 1

56 例：Prim算法 U U V0 V0 V0 V1 V2 V3 V1 V2 V3 V1 V2 V3 V4 V5 V4 V5 V4 V5
6 5 5 1 6 1 6 1 6 1 5 V1 5 V2 5 V3 5 1 5 V1 5 V2 5 V3 V1 5 V2 5 V3 6 4 3 2 6 4 3 2 6 4 3 2 V4 6 V5 V4 6 V5 V4 6 V5   6 4 注意：lowcost [ j ] 表示在 V－U 中的结点 j直接到U中结点的 所有边之中的最短边的距离。 closet[ j ]: 表示结点 j 和 U 中的 结点 k = closet[ j ] 距离当前是 最短的，且为 lowcost [ j ]； 如：s[j] 为1，表示 j 在集合U中 注意：结点j直接到U中结点的边 通常有多条。 1 2 3 4 5 1 2 3 4 5 1 1 6 5 2 1 1 1 5 5 ∞ 6 2 ∞ 4 2 lowcost closet s lowcost closet s 结点v0,v1,v2,v3,v4,v5，用下标0,1,2,3,4,5标识。

57 Prim算法 template < class VertexType, class EdgeType >
int Graph< VertexType, EdgeType > :: Prim( VertexType start, VertexType * tail, EdgeType * weight, VertexType * head ) { // start是起始顶点的数据值。tail、head、weight用于保存边的起始顶点（箭尾指向的 // 顶点）、终止顶点（箭头指向的顶点）和边的权值的一维数组。 // VertexType和EdgeType分别是顶点数据和边的权值的类型。 // AdjMatrix[j*MaxNumVertex＋k ] 保存顶点j、k之间的权值，用一维数组 // 保存邻接矩阵。即：得到邻接矩阵 [j,k] EdgeType * lowcost = new EdgeType[MaxNumVertex]; int * closet = new int[ MaxNumVertex]; int * s = new int[MaxNumVertex]; // 若s[k] = 1，那么顶点k已在顶点集U中。 int i,j,k,m; for ( m = 0; m < MaxNumVertex; m++ ) { if ( NodeList[m] = = start )break; } // 找到start结点号 if ( m >= MaxNumVertex ) {cout << "This is error!" << endl; return 0; } for ( i = 0; i < MaxNumVertex; i ++ ) { // 查询代价矩阵的第 m 行。得到在V-U中的顶点的 lowcost[i] = AdjMartrix[ m * MaxNumVertex + i]; // (从顶点出发的)最短路径。 closet[i] = m; s[i] = 0; } s[m] = 1; // 表示顶点m已在顶点集U中，m 是起始顶点。

58 Prim算法 for ( i = 0; i < MaxNumVertex -1; i ++ ) { EdgeType min;
for ( k = 0; k < MaxNumVertex; k ++ ) { if ( !s[k] ) break;} //寻找仍在顶点集V－U中的第一个顶点k min = lowcost[k]; j = k; for ( ++k; k < MaxNumVertex; k ++ ) if ( !s[k] && lowcost[k] < min ) { min = lowcost[k]; j = k; } weight[p] = lowcost[j]; // 在最小代价生成树中的本条树边的权值 head[p] = NodeList[j]; // 本条树边的一个顶点 j ∈ V-U tail[p++] = NodeList [closet[j]]; // 本条树边的另外一个顶点 s[j] = 1; // 顶点 j 并入U for ( k=0; k < MaxNumVertex; k ++ ) if ( !s[k] && AdjMatrix[j* MaxNumVertex + k] < lowcost[k] ) { lowcost[k] = AdjMatrix[j* MaxNumVertex + k]; closet[k] = j; } return p = = MaxNumVertex -1; // 如果等, 那么得到了最小代价生成树的所有树边。 }; // 边的起始、终止顶点和权值分别存放在数组tail、head和weight中。

59 Prim算法 Prim 算法 Prim 算法的基本描述
设 U：set of vertex, G: Graph, T: set of edges of mininum cost spanning tree; u, v : vertex; V: set of vertex; //初始时，V 包含所有结点 { T ＝ φ；U ＝ { V0 }; 由于 V0 在 U 中，其余各结点都在 V－U 中，可用一数组记录 V－U中的结点至 V 的路径。因为它们构成了当前横跨 U 和 V－U 两个集合的所有的边。 while ( U != V ) { 设 ( u,v ) 是一条代价最小的边，并且 u 在 U 中，v 在 V - U中。 T = T + ( u,v )；U = U + { v }; 由于 v 已被加入U 中，查找 由 v 至它的仍在 V－U中的邻接结点w的边 ，若小于原来相应的数组元素记录的最小值，则数组元素之值用该值取 代。即：该值为从w（在U-V中）到U中的所有边中最短的一条边的长度 } Prim 算法 时间代价分析：邻接矩阵：时间复杂性 O（n2），和边数无关。用于稠密图。 邻接表且使用最小化堆：时间复杂性 O((n+e)logn)。

60 Prim算法 Prim 算法在邻接表表示图并使用最小化堆的情况下的时间复杂性 O((n+e)logn) 的说明。 10
2.最小化堆中的所有结点，都将会输出。输出一个，最小化堆都会进行调整。代价为： O(nlogn) 3.在结点 v 并入 U 之后，最小堆中的某个lowcost[i] 的值可能变小，如何进行调整，使堆仍为最小化堆？由此可推出Prim算法的时间复杂性为：O((n+e)logn) 4. 求最短路径的Dijkstra 算法在邻接表表示图并用最小化堆的情况下，问题类似。 5. 请大家用上述方法，重写Dijkstra和Prim算法。 30 20 70 5 36 24 75 85 60 94 10 5 30 20 10 20 70 5 36 24 70 30 36 24 75 85 60 94 75 85 60 94

61 最短路径 注意：这里0、1、2、3、4用于标识结点V0 、 V1、V2、V3、V4。
1、从某个源点到其余各顶点的最短路径（单源最短路径问题）·权值非负情况。 实例:加权有向图 源点 V0 100 10 源点 终点 最短路径 路径长度 V0 V1 ( V0 ,V 1） V2 （V0,V3 ,V2 ） V3 （V0,V3） V4 （V0 ,V3 ,V2 ,V4） 30 V1 V4 50 10 60 V2 V3 20 加权邻接矩阵： 1 2 3 4 0 10 ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ 10 ∞ ∞ ∞ ∞ ∞ ∞ 注意：这里0、1、2、3、4用于标识结点V0 、 V1、V2、V3、V4。

62 Dijkstra算法 源点 V0 Dijkstra 算法求单源最短路径：
设 V 是该有向图的结点的集合、集合 S 是已求得最短路径的结点的集合, 求 V0 至其余各结点的最短距离。S[i]=1,表示结点i在S中，否则不在。 1、S[0] ＝ 1 ；// 结点 V0 最短路径已求得,是源点。 2、for ( i=1; i<n; i++ ) 3、 { D[i]=c[ 0, i ]; S[i]=0; } 4、for ( i=1; i<n; i++ ) 5、{ 在 V－S 中选择一个结点w；使得 D[w] 最小。将W 加入集合 S 6、 for (每一个在 V－S 中的结点 v ) { 7、 D[v]=MIN( D[v],D[w]+C[w,v]) }; 9、 } 100 10 30 V1 V4 50 10 60 V2 V3 20 S3 S2 S1 V0 100 10 10 60, 100, 100 ,60 30 V1 V4 S4 50 10 60 50, 60, ∞ V2 30, 30, V3 20 S5

63 Dijkstra算法 Dijkstra 算法: Dijkstra 算法求单源最短路径：
设 V 是该有向图的结点的集合、集合 S 是已求得最短路径的结点的集合, 求 V0 至其余各结点的最短距离。S[i]=1,表示结点i在S中，否则不在。 1、S[0] ＝ 1 ；// 结点 V1 最短路径已求得,是源点。 2、for ( i=1; i<n; i++ ) 3、 { D[i]=c[ 0, i ]; S[i]=0; Path[ v ] = -1; } 4、for ( i=1; i<n; i++ ) 5、{ 在 V－S 中选择一个结点w；使得 D[w] 最小。将W 加入集合 S // 用最小化堆选 6、 for (每一个在 V－S 中的结点 v ) //出最小的 { if (D[w]+C[w,v] < D[v ]) Path[ v ] = w; 7、 D[v]=MIN( D[v],D[w]+C[w,v]) }; //如用最小化堆实现，此处还要调整堆 9、 } 源点 V0 100 10 30 V1 V4 50 10 60 V2 V3 20 Dijkstra 算法: 路径的求法：增加Path[v] = w; Dijkstra 算法的时间复杂性: 邻接矩阵:O(n2); 考察其余n-1个结点 邻接表:O((n+e)logn)) 考察直达边即可 (用最小化堆来实现挑选最小边)

64 Dijkstra算法 Dijkstra 算法求单源最短路径：
设 V 是该有向图的结点的集合、集合 S 是已求得最短路径的结点的集合, 求 V0 至其余各结点的最短距离。S[i]=1,表示结点i在S中，否则不在。 1、S[0] ＝ 1 ；// 结点 V0 最短路径已求得,是源点。 2、for ( i=1; i<n; i++ ) 3、 { D[i]=c[ 0, i ]; S[i]=0; Path[ v ] = -1; } 4、for ( i=1; i<n; i++ ) 5、{ 在 V－S 中选择一个结点VW；使得 D[w] 最小。将W 加入集合 S // 用最小化堆选 6、 for (每一个在 V－S 中的结点 v) //出最小的 { if (D[w]+C[w,v] < D[v ]) Path[ v ] = w; 7、 D[v]=MIN( D[v],D[w]+C[w,v]) }; //如用最小化堆实现，此处还要调整堆 9、 } 注意：本书的实现程序见程序7.6。其中，AdjMatrix[j*MaxNumVertex＋k ] 保存顶点j、k之间的路径长度，替代邻接矩阵，即：Adj[j,k]。 Dijkstra 算法: 源点 100 10 30 1 4 50 10 60 2 3 20 6、7的解释： V－S 老 S X V 源点 V0 W 新 S

65 Dijkstra算法 证明：设 V0 经 S 中的j结点，到 VZ 后直接 经有向边到达结点 Vj 的路径，是所有
这些路径中最短的。如图所示，路径 p1<p2; p1<p3;p1<p4。则 p1 就是源 点 V0 至 Vj 的最短路径。 假定存在一条更短的路径，那么肯定 要经过 T - { Vj } 中的一个顶点，设 为 V3 ；但 p3 > p1，同假设矛盾，不 可能。 Dijkstra 算法: 正确性证明 设 V 是结点的集合，S 是已经得到最短 路径（由源点至本结点）的结点的集合。 T = V - S V T S Vl Vz p1 源点 Dijkstra 算法: 边的权值不可以为负值。 V0 Vm Vy V1 p2 100 -99 Vx 5 p3 V0 V2 Vn p4 Vn 注意：边的权值不可以为负值，这一点可以 从上述证明中推出。 声明：Dijkstra 算法和Prim算法本质是相同的，甚至可以用同一个函数求出，区别仅在于权值不同。

66 Dijkstra算法 Dijktra算法邻接表示图且使用最小化堆时的时间复杂性O((n+e)logn)和 Prim 算法情况类似。 10
2.最小化堆中的所有结点，都将会输出。输出一个，堆都会进行调整。代价为： O(nlogn) 3.在结点 W 并入 S 之后，最小堆中的某个D[i] 的值可能变小，如何进行调整，使堆仍为最小化堆？由此可推出 Dijkstra 算法的时间复杂性为：O((n+e)logn) 30 20 70 5 36 24 75 85 60 94 10 5 30 20 10 20 70 5 36 24 70 30 36 24 75 85 60 94 75 85 60 94

67 Floyd算法 2、每一对顶点之间的最短路径：Floyd 算法 加权有向图： 求各结点之间的最短路径 3 0 8 5 3 0 ∞ ∞ 2 0
Floyd 算法的求解过程 设 C 为 n 行 n 列的代价矩阵，c[ i, j ] 为 i ---> j 的权值。如果 i=j ；那么 c[ i, j ] = 0。如果 i 和 j 之间无有向边；则 c[ i, j ] = ∞ 1、使用 n 行 n 列的矩阵 A 用于计算最短路径。 初始时， A[ i, j ] = c[ i, j ] 2、进行 n 次迭代 在进行第 k 次迭代时，我们将使用如下的公式： Ak-1[ i, j ] Ak[ i, j ] = MIN Ak-1[ i, k ] + Ak-1[ k, j ] 注意：第 k 次迭代时，针对结点 k 进行。原 Ak-1 矩阵的第 k 行，第 k 列保持不变。左上至右下的对角线元素也不 变。 1 2 ∞ ∞ V0 V1 8 2 5 V2 左图的代价矩阵 c k Ak-1[ i, k ] Ak-1[ k, j ] Ak-1[ i, j ] i j

68 Floyd算法 实例及求解过程: 3 0 8 5 3 0 ∞ 2 0 V0 V1 8 2 5 V2 0 8 5 3 0 ∞ 2 0
设 C 为 n 行 n 列的代价矩阵，c[ i, j ] 为 i ---> j 的权值。如果 i=j ；那么 c[ i, j ] = 0。如果 i 和 j 之间无有向边；则 c[ i, j ] = ∞ 1、使用 n 行 n 列的矩阵 A 用于计算最短路径。 初始时， A[ i, j ] = c[ i, j ] 2、进行 n 次迭代 在进行第 k 次迭代时，我们将使用如下的公式： Ak-1[ i, j ] Ak[ i, j ] = M IN Ak-1[ i, k ] + Ak-1[ k, j ] 正确性证明: 对k进行归纳 （最短路径上的最大中间结点） 3 1 2 ∞ V0 V1 8 2 5 V2 ∞ ∞ A初值 A0 A1 A2

69 Floyd算法 2、每一对顶点之间的最短路径：Floyd 算法 应用范围:无负长度的圈，可有 负长度的边。 - 2 V0 V1 V2 1 1
∞ ∞ ∞ 0 ∞ ∞ 0 A1[ 0，2 ] != 2 M IN { A0[ 0，2 ], A0[ 0，1 ] + A0[ 1，2 ] } 因为 V0->V1->V0 可以有许多圈。 A初值 A1 ∞ ∞ ∞ 0 A0 3、每一对顶点之间的最短路径：Floyd 算法的程序实现，见程序7.7，时间代价: O（n3）。

70 活动网络 1、有向无环图（DAG 图） 实例 B B B E F G E F G E F G L F G L F G L F G 有向树
有向图（含环） 用途：描述工程项目或系统进行的工具 AOV(Activity on Vertex) 网络：定义结点为活动，有向边的指向表示活动执行的次序。 AOE(Activity on Edge)网络：定义结点为事件，有向边的指向表示事件的执行次序。单位是时间（时刻）。有向边定义为活动，它的权值定义为活动进行所需要的时间。 A B 10 A B

71 拓扑排序 2、拓扑排序（Topological Sort）－ AOV 网络的应用。
偏序：若集合 X 上的关系 R 是传递的、自反的、反对称的，则称 R 是集合 X 上的偏序 关系。 全序：若关系 R 是集合 X 上的偏序关系，如果对于每个 x, y 属于 X，必有 x R y 或 y R x ，则称 R 是集合 X 上的全序关系。 拓扑排序：如果有一个序列 A = a1,a2,a3…………an 是集合 X 上的元素的一个序列， 且当 i < j 时， （ai , aj ）属于 R ，则称 A 是相对于 R 拓扑排序的。 注意：且当表示（ai , aj ）属于 R， i < j 同时存在 i 和 j 是元素 ai 和 aj 在序列 A 中的序号。 用 表示（ai , aj ）属于 R， i < j ai aj ai aj 为了表示的方便，令 为前件，而 为后件。前件的序号一定要 小于后件。否则将不满足拓扑排序的定义。 用途：描述工程项目或系统进行的次序 AOV 网络：定义结点为活动，有向边的指向表示活动执行的次序。

72 拓扑排序 实例：下述集合 M 代表课程的集合，其中，1代表数学， 2代表程序设计，3代表离散数
学，4代表汇编程序设计，5代表数据结构，6代表结构程序设计, 7代表编译原理。 关系 R 课程学习的先后关系，如数学必须在离散数学之前学习。要求排一张学习 的先后次序表。 第一个输出的结点（序列中的第一个元素）：必须无前件 后件：必须等到它的前件输出之后，因此时序号才会大于前 件的序号。 无前件及后件的结点：任何时候都可输出。 序列：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 数学 1 离散数学 程序设计 3 2 汇编程序设计 数据结构 7 5 4 编译原理 6 结构程序设计

73 拓扑排序 算法的执行步骤： 1、找到全为零的第 j 列，输出 j 2、将第 j 行的全部元素置为零 3、找到全为零的第 k 列，输出 k
………………… 反复执行 3、4；直至所有元素输出完毕。 1 数学 算法（使用邻接矩阵）： 程序设计 离散数学 3 2 汇编程序设计 数据结构 编译原理 7 5 4 6 结构程序设计 1 2 3 4 5 6 7

74 拓扑排序 算法的执行步骤： 1、用一个数组记录每个结点的入度。将入度为零的结点进栈。 2、将栈中入度为零的结点V输出。
4、反复执行 2、3；直至栈空为止。 ………………… 次序执行结束，如果输出结点数等于图的结点总数，则有向图无环，否则有向图有环。 算法（使用邻接表）： 数学 1 离散数学 程序设计 3 2 汇编程序设计 数据结构 7 5 4 编译原理 6 结构程序设计

75 拓扑排序 栈 <1> 算法（使用邻接表）： 数学 算法的执行步骤： 1、用tag记录结点的入度。将入度为零的结点进栈。
2、将栈中入度为零的结点V输出。 3、根据邻接表找到结点V的所有邻接结点，并将这些邻接结点的入度减一。若某结点入度变为零，则进栈 4、反复执行 2、3；直至栈空为止。 ………………… 程序执行结束，如果输出结点数等于图的结点总数，则有向图无环，否则有向图有环。 1 离散数学 程序设计 3 2 汇编程序设计 数据结构 7 5 4 编译原理 结构程序设计 6 栈 < 3 > < 7 > < 5 > < 6 > < 4 > < 2 > ∧ tag data next adj dest cost link 1 2 3 4 5 6 7 ∧ <1> ∧

76 拓扑排序 2、Topological Sort使用单链表表示的结点表的邻接表）的程序：
template <class VertexType, class EdgeType> void Topological_Order ( Graph < VertexType , EdgeType > & graph ) { Vertex< VertexType,EdgeType > *p,*m; Stack<Vertex< VertexType,EdgeType > * > s(graph.NumVertex);   p = graph.head; while( p ) { p->tag = 0; p = p->next; } // 每个顶点的入度数清 0。 p = graph.head; while( p ) { m = graph.GetFirstNeighbor( p ); while( m ) { m->tag++; m = graph.GetNextNeighbor(p,m); } p = p->next; // 计算每个顶点的入度数。 } while( p ) { if ( p->tag == 0 ) s.Push(p); p = p->next;} //入度数为 0 的顶点进栈。 1 3 2 7 5 6 4 数学 程序设计 离散数学 汇编程序设计 数据结构 结构程序设计 编译原理 ∧ tag head ∧ ∧

77 拓扑排序 有环情况： 2、Topological Sort使用单链表表示的结点表的邻接表）的程序：
  for ( int i = 0; i < graph.NumVertex; i++ ) if ( s.IsEmpty( ) ) { cout << "There is a cycle in the Graph." << endl; return; } else { p = s.Top( ); s.Pop( ); cout << "Element " << p->data << " is in position" << i+1 << endl; //依次输出拓扑排序序列中的第1、2、…… 个顶点。 m = graph.GetFirstNeighbor(p); // 得到顶点p 的第一个邻接顶点地址。 while( m ) { // m 非空，还存在下一个邻接顶点。 if ( --m->tag == 0 ) s.Push( m ); // 入度为0 的顶点进栈。 m = graph.GetNextNeighbor(p,m); //得到下一个邻接顶点地址。 } return; 1 3 2 7 5 6 4 数学 程序设计 离散数学 汇编程序设计 数据结构 结构程序设计 编译原理 3 2 4 1 有环情况： ∧ tag head ∧ ∧

78 AOE网络 源点：表示整个工程的开始点，也称起点。 收点：表示整个工程的结束点，也称汇点。 事件结点：单位时间，表示的是时刻。
活动（有向边）：它的权值定义为活动进行 所需要的时间。方向表示起始结点事件 先发生，而终止结点事件才能发生。 2 V5 V2 1 1 3 5 2 1 8 V1 V3 V6 2 V4

79 关键路径 事件的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味着事件最早能够 发生的时刻。
事件的最迟发生时间（V l (j)）：不影响工程的如期完工，本结点事件必须发发生的时 刻。 活动的最早开始时间：e(ai ) = Ve( j ) 活动的最迟开始时间： l (ai ) = V l( k ) - dut( j , k ) 关键活动：最早开始时间 ＝ 最迟开始时间的活动 关键路径：从源点到收点的最长的一条路径，或者全部由关键活动构成的路径。 10 A B dut(j,k) j k ai 1 5 12 88 2 4 3 7 收点 起点: 1010 V1 VJ Vj Vn Vl(Vj) = 取 10-2、10-4、10-3、10-7的最小值 3;或 10 - 最长路径 7 Ve(Vj) = 88 取 1、5、12、88的最大值 88

80 关键路径 3 5 12 88 Ve(j) 的求法： 起点: V1 VJ Ve(Vj) = 3、5、12、88的最大值 88 2
V1 VJ Ve(Vj) = 3、5、12、88的最大值 88 2 注意：本图说明由已知的所有的起始结点的 Ve ，可得知终止结点的 Ve 。 如：从Ve(Vu) 、Ve (Vv) 、 Ve (Vw) 、 Ve (Vx) 可知Ve(Vj) 由源点至收点 Vu 3 1 Vv 2 9 3 V1 Vw VJ 82 6 注意：开始时只有源点的 Ve ＝ 0 已知，利用拓扑排序的序列可得到每一个结点的 Ve 。且结点的 Ve 确定次序和拓扑排序的序列相同。 Vx Ve(Vj) = Vj 的起始结点的最早发生时间 + 各自的边的权值中的和的最大值 88

81 关键路径 求事件的最早发生时间的实例 2 V5 V2 利用拓扑排序算法求事件结点的最早发生时间的执行步骤：
2 V5 V2 利用拓扑排序算法求事件结点的最早发生时间的执行步骤： 1、设每个结点的最早发生时间为0，将入度为零的结点进栈。 2、将栈中入度为零的结点V取出，并压入另一栈，用于形成逆向拓扑排序的序列。 3、根据邻接表找到结点V的所有的邻接结点，将结点V的最早发生时间 + 活动的权值 得到的和同邻接结点的原最早发生时间进行比较；如果该值大，则用该值取代原最早发生时间。另外，将这些邻接结点的入度减一。如果某一结点的入度变为零，则进栈。 4、反复执行 2、3；直至栈空为止。 1 1 3 5 2 1 V1 V3 V6 2 V4 1 3、 6 2 V5 V2 1 1 2 1 3、 3 5、 7、 8 V1 3 2 V3 V6 2 5 1 V4 5、 5 正向拓扑排序： V1 V2 V3 V4 V5 V6

82 关键路径 2 4 3 7 收点 Vl(j)）的求法： 1010 Vj Vn
Vl(Vj) = 取 10-2、10-4、10-3、10-7的最小值 3 注意：本图说明由已知的所有的终止结点的 Vl ，可得知起始结点的 Vl 。 如：从Vl(Vu) 、Vl (Vv) 、 Vl (Vw) 、 Vl (Vx) 可知 Vl(Vj) 由收点至源点 9 Vu 1 8 收点 2 Vv 1010 Vj Vn 1 8 Vw 注意：开始时只有收点的 Vl ＝ Ve(Vn) 已知，利用逆拓扑排序的序列可得到每一个结点的 Vl 。且结点的 Vl 确定次序和逆拓扑排序的序列相同。 2 5 Vx Vl(Vj) = 取终止结点的最迟发生时间 - 各自的边的权值的差的最小值 3

83 关键路径 正向拓扑排序： 实例：求事件结点的最迟发生时间 8 8 V1 V2 V3 V4 V5 V6 2 V5 V2 1 1 3 5 2 1
·逆向拓扑排序同每个结点的 VL 发生时间的确定次序是一致的。 证；·最末一个结点的 VL 最先确定。它确定之后，就可推出对相应的起始结点的影响，如上图的 V5 V4 V3 结点的 VL 当前值。 ·第二个可以确定 VL 的结点是正向拓扑排序中的倒数第二个结点，如V5 。理由：此时它已相当于出度为零的结点。即在它之前已确定 VL 的结点，对它发生的影响已全部产生(反证：如果没有全部产生，就意味着V5 V6之间还有一个结点 如Vx还对它产生影响， 边V5 Vx存在。但这样一来，它将不会是正向拓扑排序中的倒数第二个结点。证毕。) · 其余依次类推。 V1 V3 V6 2 8 V4 4、 3 2 6 V5 V2 1 1 2 1 8 6、 4 0、 0、 V1 3 2 V3 V6 2 1 5 V4 6、 5 逆向拓扑排序： V6 V5 V4 V3 V2 V1

84 关键路径 正向拓扑排序： 实例：求事件结点的最迟发生时间 8 8 V1 V2 V3 V4 V5 V6 2 V5 V2 1 1 3 5 2 1
利用逆向拓扑排序算法求事件结点的最迟发生时间的执行步骤： 1、设每个结点的最迟发生时间为收点的最早发生时间。 2、将栈中的结点V取出。 3、根据邻接表找到结点V的所有的到达结点W，将结点W的最迟发生时间 - 活动的权值得到的差同结点V的原最迟发生时间进行比较；如果该值小，则用该值取代结点V的原最迟发生时间。 4、反复执行 2、3；直至栈空为止。 V3 V6 2 8 V4 4、 3 2 6 V5 V2 1 1 2 1 8 3 6、 4 0、 0、 V1 2 V3 V6 2 1 5 V4 6、 5 逆向拓扑排序： V6 V5 V4 V3 V2 V1

85 关键路径 1 3 5 6 2 1 3 4 6 5 边 最早发生时间 最迟发生时间 实例的事件结点的最早发生时间 V1 V2 1 6 2 V5
1 3 5 6 2 1 3 4 6 5 V1 V2 1 6 2 V5 V2 V1 V3 1 1 3 5 2 1 3 8 V1 V4 关键活动 V1 V3 V6 2 V2 V3 5 V4 V2 V5 实例的事件结点的最迟发生时间 V3 V4 3 6 2 V5 V2 V3 V6 1 1 3 5 2 1 4 8 V4 V5 关键活动 V1 V3 V6 2 V4 V6 5 V5 V6 V4 关键活动

86 关键路径 实例的关键路径（粗大的黑色箭头所示） 6 1 2 V5 V2 3 1 6 1 3 5 1 2 1 3 8 V1 V3 V6 2 4
3 8 V1 V3 V6 2 4 8 5 V4 5 注意：关键路径可有多条 缩短工期必须缩短关键活动所需的时间 时间代价：图中的结点和边都要访问到，故：O(e+n)。