【数据结构】树

1、第6章 树(6学时),树 二叉树 树和森林 哈夫曼树及应用,6.1 树,树形结构是一类重要的非线性结构，树形结构是结 点之间有分支、分层关系的结构。 树的定义：树是n(n0)个结点的有限集。 它满足以下两个条件： （1）有且仅有一个特定的称为根的结点。 （2）其余的结点可分为m个互不相交的有限集合T1, T2,Tm，其中，每个集合又都是一棵树（子 树）。 树的表示,6.1 树,结点的度：一个结点的子树个数称为该结点的度。 树的度：一棵树中结点度的最大值。 叶子（终端结点）：度为0的结点。 分支结点（非终端结点）：度不为0的结点。 内部结点：除根结点之外的分支结点。 孩子：树中某个结点的子树的根

2、称为个结点的孩子。 双亲：该结点则为孩子的双亲。 兄弟：同一个双亲的孩子。 路径：若树中存在一个结点序列k1,k2,kj，使得ki是ki+1的双亲 (1ij)，称该结点序列是从k1到kj的一条路径。 祖先：若树中结点k到ks存在一条路径，则称k是ks的祖先。 子孙：ks是k的子孙。,6.1 树,层次：结点的层次是从根开始算起(根为1层)。 高度：树中结点的最大层次称为树的高度或深度。 有序树：若将树中每个结点的各子树看成是从左到右有 秩序的。 无序树：否则称为无序树。 森林：是m(m0)棵互不相交的树的集合。 (树形结构的逻辑特征可用树中结点之间的父子关系来描述),6.1 树,树的基本操作有下

3、列几种： （1）初始化操作。 （2）求根函数。 （3）求双亲函数。 （4）求孩子结点函数。 （5）求右兄弟函数。 （6）建树函数。 （7）插入子树操作。 （8）删除子树操作。 （9）遍历操作。 （10）清除结构操作。,6.2 二叉树,概念 性质 存储结构 遍历 线索化,6.2 二叉树,概念 定义：二叉树是个结点的有限集，它或者是空集， 或者由一个根结点及两棵不相交的分别称作 这个根的左子树和右子树的二叉树组成。 二叉树的五种基本形态,6.2 二叉树,二叉树的性质 1、二叉树第i层上的结点数目最多为2i-1(i0)。 归纳法证明： 归纳基础：i=1时，有2i-1=20=1。 归纳假设：假设对所有

4、的j(1ji)命题成立，即第j层上至多 有2j-1个结点，证明j=i时命题成立。 归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点，由于 二叉树的每个结点至多有两个孩子，故第i层上的 结点至多是第i层上的最大结点数的2倍，即j=i时 该层上至多有2*2i-2=2i-1个结点，故命题成立。,6.2 二叉树,2、深度为k的二叉树至多有2k-1个结点。 证明：在具有相同深度的二叉树中，仅当每一层都含有最多结点时， 其树中结点数最多。因此，利用性质1可得，深度为的二叉树 中至多含有的结点数为： 20+21+2k-1=2k-1 故命题正确。 3、在任意一棵二叉树中，若终端结点的个数为n0，度为2

5、 的结点数为n2，则n0=n2+1。 证明：因为二叉树中所有结点的度数均不大于2，所以结点总数应等 于0度结点数、1度结点数和2度结点数之和，即： n=n0+n1+n2 ,6.2 二叉树,另一方面，1度结点有一个孩子，2度结点有两个孩子。所以， 二叉树中孩子结点总数是n1+2n2，二叉树中只有根结点不是任何结点 的孩子，故二叉树中的结点总数又可以表示为： n=n1+2n2+1 由式和式得到： n0=n2+1 两种特殊形式的二叉树： 满二叉树：一棵深度为k且有2k-1个结点的二叉树。 完全二叉树：若一棵二叉树至多只有最下面两层上结点的度数可以 小于2，并且最下层上的结点都集中在该层最左边的若 干

6、位置上，则此二叉树称为完全二叉树。,6.2 二叉树,4、具有n个结点的完全二叉树的深度为log2n +1 证明：设所有完全二叉树的深度为k，由完全二叉树的定义可知，它 的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。由 于完全二叉树深度为k，故第k层上还有若干个结点，因此， 该完全二叉树的结点个数n2k-1-1。 另一方面，由性质2可知n2k-1，即： 2k-1-1 n 2k-1 由此可推出： 2k-1 n 2k-1 取对数后有: k-1 log2n k 因为k为整数，故有 k-1= log2n ,由此可得： k= log2n +1,6.2 二叉树,5、如果对一棵有n个结点的完

7、全二叉树，则对任一结点有： （1）若i=1，则ki是根结点，无双亲；若i1,则ki的双亲 编号为int(i/2)。 （2）若2in，则ki的左孩子的编号是2i；2in,则无左 孩子。 （3）若2i+1n,则ki右孩子的编号是2i+1;2i+1n,则无 右孩子。 （4）若i为奇数且不为1，则ki的左兄弟的编号是i-1；否 则ki无左兄弟。 （5）若i为偶数且小于n，则ki的右兄弟的编号是i+1；否 则ki无右兄弟。,6.2 二叉树,二叉树的存储结构 1）顺序存储结构: 对完全二叉树而言，既简单又节省存储空间，但对非完全二叉树，必须按完全二叉树的形式来存储树中的结点，这将造成存储空间的浪费。 A

8、0 B 0 0 0 C 1 2 3 4 5 6 7 A 0 B 0 0 0 C,6.2 二叉树,2）链式存储结构 设计不同的结点结构可构成不同的链式存储结构。通常采用二叉链表的形式，即： lchild data rchild typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; *BiTree;,6.2 二叉树,二叉链表的生成 Status CreateBiTree(BiTree ,6.2 二叉树,A B C D E F T A B C D E F ,6.2 二叉树,二叉树的遍历 遍历：是指沿某条搜索路径

9、周游二叉树，对树中每个 结点访问一次且仅访问一次。 前序遍历（DLR）：访问根的操作是在遍历其左、右 (先根) 子树之前进行的。 中序遍历（LDR）：访问根的操作是在遍历其左、右 (中根) 子树之中进行的。 后序遍历（LRD）：访问根的操作是在遍历其左、右 (后根) 子树之后进行的。,6.2 二叉树,A B C D E F 前序遍历序列：ABDCEF 中序遍历序列：DBAECF 后序遍历序列：DBEFCA,6.2 二叉树,前序遍历递归算法： Status PreOrder(BiTree T) if (T) Visit(T-data); PreOrder(T-lchild); PreOrder(

10、T-rchild); ,6.2 二叉树,中序遍历递归算法： Status InOrder(BiTree T) if (T) InOrder(T-lchild); Visit(T-data); InOrder(T-rchild); ,6.2 二叉树,后序遍历递归算法： Status PostOrder(BiTree T) if (T) PostOrder(T-lchild); PostOrder(T-rchild); Visit(T-data); ,6.2 二叉树,InOrder( Push(S, T); while (! StackEmpty(S) while (GetTop(S, p) ,6

11、.2 二叉树,“遍历”是二叉树各种操作的基础。 由上讨论得知： 遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。 这实质上是对一个非线性结构进行线性化。,练习题,已知某二叉树的前序遍历序列为ABDEGCFHIJ， 中序遍历序列为：DBGEAHFIJC，请写出该二叉树 的后序遍历序列？ 求某二叉树的叶子数。,参考答案：,A B C D E F G H I J 后序遍历序列: DGEBHJIFCA,参考答案：,Status countleaf(BiTree T, int ,6.2 二叉树,结点的结构： lchild ltag data rt

12、ag rchild 其中：ltag= 0 指示结点的左孩子 1 指示结点的前驱 rtag= 0 指示结点的右孩子 1 指示结点的后继 线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。 线索：其中指向结点的前驱和后继的指针，叫做线索。 线索二叉树：加上线索的二叉树称之为线索二叉树。 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。,6.2 二叉树,中序线索二叉树: A NULL NULL B E C D F G H r I,6.2 二叉树,中序遍历建立线索化链表的算法 Status InOrderThreading(BiThrTree ,6.2 二叉树

13、,Status InThreading(BiThrTree p) if (p) InThreading(p-lchild); if (! P-lchild) p-Ltag=Thread; p-lchild=pre; if (! Pre-rchild) pre-Rtag=Thread; pre-rchild=p; pre=p; InThreading(p-rchild); ,6.2 二叉树,线索二叉树的三种常用运算: 查找某结点P在指定次序下的前驱和后继 遍历线索二叉树 线索二叉树的插入,6.2 二叉树,查找某结点P在指定次序下的后继 Statust inordernext(BiThrptr p

14、) if (p-Rtag=1) return (p-rchild); else q=p-rchild; while (q-Ltag=0) q=q-lchild; return (q); ,6.2 二叉树,查找某结点P在指定次序下的前驱 Statust inorderpre(BiThrptr p) if (p-Ltag=1) return (p-lchild); else q=p-lchild; while (q-Rtag=0) q=q-rchild; return (q); ,练习题,画出下列二叉树的前序、中序和后序线索二叉树。 A B C D E F G H,6.3 树和森林,树的存储结构

15、树和森林与二叉树的转换 树和森林的遍历,6.3 树和森林,树的存储结构 双亲表示法 孩子表示法 孩子兄弟表示法,6.3 树和森林,树和森林与二叉树的转换 A A B B C D E C F G D E F G H I J H I J,6.3 树和森林,A A E G B E B C D F H I C F G D H I,6.3 树和森林,树和森林的遍历 树的先序遍历：先访问树的根结点，然后依次先序遍历根的每棵 子树。 树的后序遍历： 先依次后序遍历每棵子树，然后访问根结点。 （参见：P137图6.16） 注: 先序遍历一棵树恰好等价于先序遍历该树对应的二叉树; 后序遍历一棵树恰好等价于中序遍

16、历该树对应的二叉树;,6.3 树和森林,树和森林的遍历 森林的先序遍历: (1) 先访问森林中第一棵树的根结点; (2) 先序号遍礼第一棵树中根结点的子树森林; (3) 先序遍历除去第一棵树之后剩余的树构成的森林。 森林的中序遍历： (1) 中序遍历森林中第一棵树的根结点的子树森林; (2) 访问第一棵树的根结点; (3) 中序遍历除去第一棵树之后剩余的树构成的森林。 （参见：P138图6.17）,6.4 哈夫曼树及应用,概念 路径: 从树中一个结点到另一个结点之间的分支构成了这两个结 点之间的路径。 路径长度: 路径上的分支数目称做路径长度。 树的路径长度: 从树根到树中每一结点的路径长度之

17、和。 结点的带权路径长度: 从该结点到树根之间的路径长度与结点上 权的乘积。 树的带权路径长度: 树中所有叶子结点的带权路径长度之和 （WPL）。 （参见：P144图622）,6.4 哈夫曼树及应用,最优二叉树 (哈夫曼树) 带权路径长度WPL最小的二叉树，称之为最优二叉树。 （如何构造最优二叉树？） 哈夫曼算法： （1） 根据给定的n个权值 w1,w2,wn 构成n棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点， 其左右子树均为空。 （2） 在F中选取每棵根结点的权值最小的树作为左右子树构造新的二叉树， 且置新的二叉树的根结点的权值为其左右子树上根结点的

18、权值之和。 （3） 在F中删除这两棵树，同时将新得到的二叉树加入F中。 （4） 重复（2）和（3），直到F含一棵树为止。 (参见：P146图624),6.4 哈夫曼树及应用,哈夫曼编码 前缀编码：任意一个字符的编码都不是另一个字符的编码的前缀。 0 1 a的编码： 0 a b的编码： 10 0 1 c的编码：110 b d的编码：111 0 1 c d,上机题：,以（P148-例6-2）为例，根据算法6.12设计哈夫曼编码。,第7章 图（6学时）,图的概念 图的存储结构(邻接矩阵、邻接链表等) 图的遍历(DFS和 BFS) 生成树和最小生成树(Prim算法和 Kruskal算法) 拓扑排序 关

19、键路径 最短路径(Dijkstra算法和 Floyd算法),7.1 图的概念,图是一种复杂的非线性结构 图：由顶点集V和边集E组成，记为： G=（V，E） 例： A A A 3 B 5 8 4 9 E B B C 6 9 C 2 D C D (G1) (G2) (G3),7.1 图的概念,有向图：若图G中的每条边都是有方向的，则称G为有向图。 例：图G1 V(G1)=A, B, C E(G1)=, , 无向图：若图G中的每条边都没有方向的，则称G为无向图。 例：图G2 V(G2)=A, B, C, D E(G2)=(A, B), (A, C), (A, D), (B, C), (B, D),

20、(C, D) 网络：若将图的每条边都赋上一个具有某种有意义的数（权）， 则称这种带权的图为网络。 例：图G3 有向完全图：若有向图G的顶点数n和边数e恰有e=n(n-1)条边。 无向完全图：若有向图G的顶点数和边数恰有e=n(n-1)/2条边。,7.1 图的概念,关联：若(vi, vj)是一条无向边，则称顶点vi和vj互为邻接点，或称 vi和vj相邻接；并称边(vi, vj)关联于顶点vi和 vj ，或称边 (vi, vj)与顶点vi和 vj相关联。 子图：设G=（V，E）是一个图，若V是V的子集，E是E的子集， 且E中的边所关联的顶点均在V中，则G=（V，E）也 是一个图，则称其为G的子图。

21、 例： A A A B C B C D,7.1 图的概念,度：无向图中顶点V的度是关联于该顶点的边的数目，记为D(V)。 若G为有向图，则以顶点V为终点的边的数目称为V的入度， 记为ID(V)；把以顶点V为始点的边的数目称为V的出度，记 为OD(V)；那么顶点V的度则定义为该顶点的入度与出度之和。 结论：无论是有向图还是无向图，顶点数n、边数e和度数之间有如 下关系： E= (D(vi)/2 i: 1n 例：图G1： e=(D(A)+D(B)+D(C)/2=(1+1)+(1+2)+(1)/2=3 图G2： e=(D(A)+D(B)+D(C)+D(D)/2=12/2=6,7.1 图的概念,路径：

22、在图G中，若存在一个顶点序列vp, vi1, vi2, , vq，使得 (vp,vi1), (vi1,vi2), ,(vin, vq)均属于E(G)，则称到顶点vp到vq 存在一条路径。 路径长度：该路径上边的数目。 简单路径：若一条路径上除vp和vq可以相同外，其余顶点均不相 同，则称此路径为一条简单路径。 简单回路：起点和终点相同的简单路径。,7.1 图的概念,连通：在无向图G中，若从顶点vi到vj有路径，则称vi和vj是连通的。 连通图：若V(G)中任意两个不同的顶点vi和vj都连通，则称G为连 通图。 连通分量：无向图G的极大连通子图称为G的连通分量。 （参见：P159图7.3） 强连

23、通图：在有向图中，若对于V(G)中任意两个不同的顶点vi和vj 都存在从vi到vj以及vj到vi的路径，则称G是强连通图。 强连通分量：有向图G的极大连通子图称为G的强连通分量。 （参见：P159图7.4）,7.2 图的存储结构,图的常用存储表示方法有：邻接矩阵（数组）、邻接表、邻接多 重表和十字链表等。 邻接矩阵表示法 邻接矩阵：是表示顶点之间相邻关系的矩阵。 设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵。 Aij= 1 若(vi, vj)或是E(G)中的边 0 若(vi, vj )或不是E(G)中的边 (若为网时，则在边存在的位置写上权值w ),7.2 图的存

24、储结构,v1 v4 0 1 1 1 A1= 1 0 1 1 1 1 0 0 v2 v3 1 1 0 0 v1 v4 0 0 0 1 0 0 0 1 0 0 v5 A2= 1 0 0 0 0 v2 v3 1 1 0 0 0 0 0 1 1 0,7.2 图的存储结构,Status CreateUDN(Mgraph ,7.2 图的存储结构,邻接链表表示法 边表：对于无向图而言，vi的邻接表中每一个表结点都对应于与vi 相关联的一条边，因此，称之为边表。 出边表：对于有向图而言， vi的邻接表中每一个表结点都对应于 以vi为始头射出的一条边，因此，称之为出边表。 入边表：对于有向图而言， vi的邻接表

25、中每一个表结点都对应于 以vi为终点射入的一条边，因此，称之为入边表。 （以入边表表示的称之为逆邻接表）,7.2 图的存储结构,邻接链表表示法 （ 顶点表） （ 边表） v1 v4 1 v1 2 3 4 2 v2 1 3 4 3 v3 1 2 v2 v3 4 v4 1 2 v1 v4 1 v1 4 2 v2 3 v5 3 v3 1 v2 v3 4 v4 1 2 5 v5 3 4,7.2 图的存储结构,逆邻接链表表示法 （ 顶点表） （ 入边表） v1 v4 1 v1 3 4 2 v2 4 v5 3 v3 2 5 4 v4 1 5 v2 v3 5 v5,7.3 图的遍历,图的遍历：从图的某一顶点

26、出发，沿着某条搜索路径 对图中所有顶点仅作一次访问的过程。 深度优先搜索（Depth_First Search，DFS）遍历：首先访问出发点vi，并将其标记为已访问过，然后依次从vi出发搜索vi的每一个邻接点vj，若vj未被访问过，则以vj为新的出发点继续进行深度优先搜索。它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。（它类似于树的先根遍历） 按访问顶点的走向次序所得到的顶点序列，称为该图的深度优先搜索遍历序列，简称为DFS序列。 由此，当以邻接表作存储结构时，深度优先搜索遍历的时间复杂度为O(n+e)。 （参见：P168-图7.13（a）、（b）,7.3 图的遍历,深度优先搜索

27、遍历算法（邻接表） Void DFSTraverse(Graph G, status (*visit)(int v) 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=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w) if (! Visitedw) DFS(G, w); ,7.3 图的遍历,广度优先搜索

28、（Breadth_First Search，BFS）遍历：首先访问出发点vi，并将其标记为已访问过，接着依次访问vi的所有邻接点，然后再依次访问与其邻接的所有未曾访问过的顶点，依次类推，直至图中所有和初始出发点vi有路径相通的顶点都已访问过为止。它的特点是尽可能先对横向进行搜索，故称之为广度优先搜索。（它类似于树的按层次遍历） 按访问顶点的走向次序所得到的顶点序列，称为该图的广度优先搜索遍历序列，简称为BFS序列。 由此，当以邻接表作存储结构时，广度优先搜索遍历的时间复杂度为O(n+e)。 （参见：P168-图7.13（a）、（c）,7.3 图的遍历,Void BFS(Graph G, sta

29、tus (* visit) (int v) for (v=0; vG.vexnum; +v) visitedv=FALSE; InitQueue(Q); for (v=0; vG.vexnum; +v) if (! Visitedv) EnQueue(Q, v); while (! QueueEmpty) DeQueue(Q, u); visitedu=TRUE; Visit(u); for (w=FirstAdjVex(G, u); w; w=NextAdjVex(G, u, w) if (! visitedw) EnQueue(Q, w ); ,练习题:,给出图G的邻接矩阵和邻接表两种存储

30、结构，并分别给出图G的DFS序列和BFS序列。 1 2 3 4 5 （图G）,上机题：,建立图G的邻接矩阵和邻接链表，并在此存储结构上进行DFS遍历和BFS遍历，输出DFS序列和BFS序列。,7.4 生成树和最小生成树,生成树：一个连通图G的子图，如果是一个包含G的所有顶点的树 （无回路的连通图），则该子图称为G的生成树（它是连 通图的一个极小连通子图）。 如何求得生成树？ 设图G是一个具有n个顶点的连通图，则从G的任一顶点出发，作一次深度优先搜索或广度优先搜索，就可将G中所有n个顶点都访问到，访问中经过n-1条边，这n-1条边将n个顶点连接成G的极小连通子图，它就是G的一棵生成树。 通常：由

31、深度优先搜索得到的生成树称为深度优先生成树，简称DFS 生成树。 由广度优先搜索得到的生成树称为广度优先生成树，简称BFS 生成树。,7.4 生成树和最小生成树,v1 v2 v3 v4 v5 v6 v7 v8 (图G) v1 v1 v2 v3 v2 v3 v4 v5 v6 v7 v4 v5 v6 v7 v8 v8 （DFS生成树） （BFS生成树）,7.4 生成树和最小生成树,最小生成树: 对于连通网络G， 边是带权的，因而G的生成树的各 边也是带权的,把生成树的各边的权值总和称为生 成树的权，则权最小的生成树称为G的最小生成树。 MST性质：假设N=（V,E）是一个连通网，U是顶点集V的一个

32、非空 子集。若（u,v）是一条具有最小权值的边，其中uU， vV-U，则必存在一棵包含边（u,v）的最小生成树。 利用MST性质构造最小生成树的算法： Prim算法（参见：P174-图7.16、图7.17和算法7.9） Kruskal算法（参见：P176-图7.18）,7.4 生成树和最小生成树,Void MiniSpanTree_Prim(MGrph G, VertexType u) k=LocateVex(G, u); for (j=0; jG.vexnum; +j) if (j !=k) closedgej=u, G.arcskj.adj; closedgek.lowcost=0; fo

33、r (i=1; iG.vexnum; +i ) k=mininum(closedge); printf( closedgek.adjvex, G.vexsk); closedgek.lowcost=0; for (j=0; jG.vexnum; +j) if (G.arcskj.adjclosedgej.lowcost) closedgej=G.vexsk, G.arcskj.adj; ,练习题,使用Prim和Kruskal算法构造图G的一棵最小生成树。 6 5 5 1 5 3 6 4 2 6 ,7.5 拓扑排序,拓扑排序：由某个集合上的一个偏序得到该集合上的 一个全序，这个操作称之为拓扑排序

34、。 偏序：若集合X上的关系R是自反的、反对称的和传递 的，则称R是集合X上的偏序关系。 全序：设R是集合X上的偏序，如果对每个x,yX，必 有xRy，或yRx，则称R是集合X上的全序关系。 AOV网：用顶点表示活动，用弧表示活动间的优先关系 的有向图称为AOV（Activity On Vertex Network）网.,7.5 拓扑排序,如何进行拓扑排序？ （1）在有向图中选一个没有前驱的顶点且输出之。 （2）从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前 图中不存在无前驱的顶点为止。 （参见：P182-图7.28）,7.5 拓扑排序,Status Topo

35、logicalsort(ALGraph G) FindInDegree(G, indegree); InitStack(S); for (i=0; inextarc) k=p-adjvex; if(! (-indegreek) Push(S, k); if(countG.vexnum) return ERROR; else return OK; ,7.6 关键路径,AOE(Activity On Edge network)网： 即边表示活动的网络。AOE网是一个带权的有向图。 其中：顶点表示事件，边表示活动。 源点：网中只有一个入度为零的顶点。 汇点：网中只有一个出度为零的顶点。 关键路径：从

36、源点到汇点的最长路径。 关键活动：关键路径上的所有活动都是关键活动。 AOE网待研究的问题是： （1）完成整个工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？,7.6 关键路径,以P183-图7.29为例可见： （1）整个工程需要18天才能完成。 （2）影响工程的关键路径是： ( v1 v2 v5 v8 v9 )：18天 ( v1 v2 v5 v7 v9 )：18天,7.6 关键路径,关键活动：把e(i)=l(i)的活动ai称为关键活动。 其中： e(i)表示活动ai 的最早开始时间。（例： a6：5） l(i)表示活动ai 的最迟开始时间。（例： a6：8） 关系式： e(i)=

37、ve(j) l(i)=vl(k)-dut() 其中：ve(j)：事件vj的最早发生时间（是从源点v1到顶点 vj的最长路径的长度, 例：ve(5)=7）。 vl(j)：事件vj的最迟发生时间（在不推迟整个工程完成的前提 下，应等于汇点vn的最早发生时间ve(n)减去vk到vn的最 长路径长度，例：vl(5)=7）。 dut()：表示边的权值。,7.6 关键路径,事件vj的最早发生时间ve(j)的计算可用下列递推公式： ve(1)=0 ve(j)=MAX ve(i)+dut() ve(1)=0 ve(2)= ve(1)+dut()=0+6=6 ve(3)= ve(1)+dut()=0+4=4 v

38、e(4)= ve(1)+dut()=0+5=5 ve(5)= MAX ve(2)+dut(), ve(3)+dut() =MAX6+1, 4+1=7 ve(6)= ve(4)+dut() =5+2=7 ve(7)= ve(5)+dut()=7+9=16 ve(8)= MAXve(5)+dut(), ve(6)+dut()=MAX7+7,7+4=14 ve(9)= MAXve(7)+dut(), ve(8)+dut()=MAX16+2,14+4=18,7.6 关键路径,事件vj的最迟发生时间vl(j)的计算可用下列递推公式： vl(n)=ve(n) vl(j)=MIN vl(k)-dut() v

39、l(9)=ve(9)=18 vl(8)= vl(9)-dut()=18-4=14 vl(7)= vl(9)-dut()=18-2=16 vl(6)= vl(8)-dut()=14-4=10 vl(5)= MIN vl(8)-dut(), vl(7)-dut() =MIN14-7, 16-9=7 vl(4)= vl(6)-dut() =10-2=8 vl(3)= vl(5)-dut()=7-1=6 vl(2)=vl(5)-dut()=7-1=6 vl(1)= MINvl(2)-dut(), vl(3)-dut(), vl(4)-dut() =MIN6-6, 6-4, 8-5=0,7.6 关键路径

40、,利用ve和vl的值，按公式即可计算出各活动ai的最早 开始时间e(i)和最迟开始时间l(i)，结果如下： a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e 0 0 0 6 4 5 7 7 7 16 14 l 0 2 3 6 6 8 7 7 10 16 14 l-e 0 2 3 0 2 3 0 0 3 0 0 （从中可以看出： a1、a4、a7、a8、a10 和 a11是关键活动。）,7.6 关键路径,由上述讨论可以得出求关键活动算法的基本步骤： （1）对AOE网进行拓扑排序，同时按拓扑排序序列的次 序求出各顶点事件的最早发生时间ve，若网中有回 路，则算法终止，否则执

41、行步骤（2）。 （2）按拓扑序列的逆序求出各顶点事件的最迟发生时间 vl。 （3）根据各顶点事件的ve值vl值，求出各活动ai的最早 开始时间e(i)和最迟开始时间l(i)，若e(i)=l(i)， 则ai为关键活动。,7.6 关键路径,Status TopologicalOrder(ALGraph G, Stack ,7.6 关键路径,Status CriticalPath(ALGraph G) if (! ToplogicalOrder(G, T) return ERROR vl0.G.vexnum=ve0.G.vexnum-1; while (! StackEmpty(T) for (Pop(T, j), p=G.vexticesj.firstarc; p; p=p-nextarc) k=p-adjvex; dut=*(p-info); if (vlk-dutnextarc) k=p-adjvex; dut=*(p-info); ee=vej; el=vlk-dut; tag= (ee=el) ? * : ; printf(j, k, dut, ee, el, tag ); ,上机题,对图