第13章非线性结构

《第13章非线性结构》由会员分享，可在线阅读，更多相关《第13章非线性结构（35页珍藏版）》请在装配图网上搜索。

1、本章课件制作：靳展第三部分第三部分 数据结构基础数据结构基础本章内容（树形结构）本章内容（树形结构）树的基本概念树的基本概念 二叉树的基本概念和性质二叉树的基本概念和性质 二叉树的存储结构二叉树的存储结构 二叉树的遍历二叉树的遍历 C+C+中的二叉树类中的二叉树类 树、森林与二叉树的转换树、森林与二叉树的转换 哈夫曼树哈夫曼树 本章内容（图形结构）本章内容（图形结构）图的概念图的概念 图的存储结构图的存储结构 图的遍历图的遍历 图的生成树和最小生成树图的生成树和最小生成树 最短路径最短路径 拓扑排序拓扑排序 关键路径关键路径 树的基本概念树的基本概念 1.树的特点树的特点2.树的定义树的定义

2、树树是是n(n0)个数据元素的有限集合。它满足以下两个数据元素的有限集合。它满足以下两个条件：个条件：有且仅有一个特定的称为根的元素；有且仅有一个特定的称为根的元素；其余元素分为（其余元素分为（）个互不相交的有限集）个互不相交的有限集合合1、2、，其中每个集合又都是一棵树并、，其中每个集合又都是一棵树并称其为根的称其为根的子树子树。树形结构是一类非常重要的树形结构是一类非常重要的非线性结构，适合于描述数据元非线性结构，适合于描述数据元素之间的层次关系素之间的层次关系 树的常用术语树的常用术语 双亲、子女、边双亲、子女、边:若结点是结点的一棵子树的根，则称做的若结点是结点的一棵子树的根，则称做的

3、“双亲双亲”称做的称做的“子女子女”；有序对，称做从到的；有序对，称做从到的“边边”。兄弟：兄弟：具有同一双亲的结点具有同一双亲的结点。路径、路径长度：路径、路径长度：若树中存在着一个结点的序列若树中存在着一个结点的序列12j，使，使ki是是ki+1（）的双亲，则称该结点序列为从）的双亲，则称该结点序列为从k1到到kj的一条路径；路径长度的一条路径；路径长度 等于等于-，它是该路径所经过的边的数目，它是该路径所经过的边的数目。结点的层数：结点的层数：根结点层数为，其余结点层数等于其双亲结点层数加根结点层数为，其余结点层数等于其双亲结点层数加。树的深度（高度）：树的深度（高度）：即树中层数最大的

4、结点的层数即树中层数最大的结点的层数。结点的度数、树的度数：结点的度数、树的度数：一个结点子女的个数称为该结点的一个结点子女的个数称为该结点的“度数度数”。树中度数最大的结点的度数叫做树中度数最大的结点的度数叫做“树的度数树的度数”。树叶、分支结点：树叶、分支结点：度数为的结点叫做度数为的结点叫做“树叶树叶”；度数大于的结点叫做；度数大于的结点叫做“分分 支结点支结点”或或“内结点内结点”。有序树、无序树：有序树、无序树：若将树中每个结点的各个子树看成从左到右有序的，若将树中每个结点的各个子树看成从左到右有序的，则称该树为有序树；否则为无序树则称该树为有序树；否则为无序树。森林：森林：（）棵互

5、不相交的树的集合称为森林）棵互不相交的树的集合称为森林。树的常用术语举例树的常用术语举例 是的是的双亲双亲，是的，是的子女子女，是从到的，是从到的边边。l、互为、互为兄弟兄弟，而和不是兄弟，而和不是兄弟。l ADIN是从结点到结点的一条是从结点到结点的一条路径路径，其，其长度长度为为。层数层数为的结点有，为的结点有，层数层数为的结点有、为的结点有、。树的深度树的深度为为。、的、的度度数分别为、；数分别为、；树的度数树的度数为为。、都是、都是树叶树叶，其余结点都是，其余结点都是分支结点分支结点。森 林二叉树的基本概念二叉树的基本概念二叉树二叉树是（是（）个结点的有限集合。它或者是空集）个结点的有

6、限集合。它或者是空集（），或者由一个根结点及两棵互不相交的、分别称为（），或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。这个根的左子树和右子树的二叉树组成。1.二叉二叉树的定义树的定义 2.二叉树五种基本形态二叉树五种基本形态 二叉树的子树有左、右之分，树的子树是相同的。二叉树的子树有左、右之分，树的子树是相同的。二叉树可以是空，而树不能为空。二叉树可以是空，而树不能为空。3.树和二叉树的差别树和二叉树的差别二叉树的性质二叉树的性质性质性质 二叉树第层上的结点数目最多为二叉树第层上的结点数目最多为2i（）。）。性质性质 深度为的二叉树至多有深度为的二叉树至多有2

7、k+1-1个结点（个结点（）。）。性质性质 在任意一棵二叉树中，若终端结点的个数为在任意一棵二叉树中，若终端结点的个数为n0、度数为的结点、度数为的结点的个数为的个数为n2，则，则n0=n2+1。1.二叉树的性质二叉树的性质2.两种特殊的二叉树两种特殊的二叉树满二叉树满二叉树 完全二叉树完全二叉树完全二叉树性质完全二叉树性质 性质性质4 具有个结点的完全二叉树的深度为具有个结点的完全二叉树的深度为 log2n 性质性质5 若对一棵有个结点的完全二叉树，按自顶向下、同层由左到右顺序依次若对一棵有个结点的完全二叉树，按自顶向下、同层由左到右顺序依次为其每个结点从为其每个结点从0开始编号，则对编号为

8、的结点开始编号，则对编号为的结点ki（n-1）则有：）则有：若若0，则，则ki双亲结点的编号为双亲结点的编号为 (i-1)/2 若若=，则，则ki是根结点。是根结点。若若2i+1n，则，则ki左子女结点的编号是左子女结点的编号是2i+1，否则，否则ki无左子女。无左子女。若若2i+2n，则，则ki右子女结点的编号为右子女结点的编号为2i+2，否则，否则ki无右子女。无右子女。二叉树的存储结构二叉树的存储结构 对完全二叉树，利用性质对完全二叉树，利用性质5，将其所有结点按编号顺序依次存储在一维数组里。，将其所有结点按编号顺序依次存储在一维数组里。对一般二叉树，需要加上一些并不存在的对一般二叉树，

9、需要加上一些并不存在的“虚结点虚结点”，转换为完全二叉树的形式，转换为完全二叉树的形式。1.顺序存储结构顺序存储结构 二叉树的存储结构二叉树的存储结构 2.链式存储结构链式存储结构 template template class BinTree;/二叉树类BinTree的前视声明template class Nodefriend class BinTree;/定义二叉树类BinTree为友元 public:Node():lchild(NULL),rchild(NULL)/无参构造函数 Node(T val,Node*lptr=NULL,Node*rptr=NULL)/带参构造函数data=va

10、l;lchild=lptr;rchild=rptr;链接存储时结点的结构链接存储时结点的结构二叉树的遍历二叉树的遍历先序遍历先序遍历 访问根结点，先序遍历左子树，先序遍历右子树。访问根结点，先序遍历左子树，先序遍历右子树。中序遍历中序遍历 中序遍历左子树，访问根结点，中序遍历右子树。中序遍历左子树，访问根结点，中序遍历右子树。后序遍历后序遍历 后序遍历左子树，后序遍历右子树，访问根结点。后序遍历左子树，后序遍历右子树，访问根结点。层次遍历层次遍历 按层数由小到大、同一层从左到右顺序依次访问二叉树的各个结点按层数由小到大、同一层从左到右顺序依次访问二叉树的各个结点 先序访问序列先序访问序列：AB

11、DGECF中序访问序列中序访问序列：DGBEAFC后序访问序列后序访问序列：GDBEAFC层次访问序列层次访问序列：ABCDEFG 二叉排序树类二叉排序树类template class BinTree public:BinTree():root(NULL)/构造一棵空树 BinTree()Destroy(root);/析构函数 void insertNode(T val)/向二叉树插入值为val的结点 insertNode(root,val);void PreOrder()PreOrder(root);/前序遍历二叉树 void InOrder()InOrder(root);/中序遍历二叉树

12、void PostOrder()PostOrder(root);/后序遍历二叉树 void LevelOrder()LeverOrder(root);/层次遍历二叉树 private:Node*root;/根结点指针 void insertNode(Node*&t,T val);/向t指向的二叉树中插入结点 void PreOrder(Node*t);/前序遍历t指向的二叉树 void InOrder(Node*t);/中序遍历t指向的二叉树 void PostOrder(Node*t);/后序遍历t指向的二叉树 void LeverOrder(Node*t);/层次遍历t指向的二叉树 voi

13、d Destroy(Node*t);/删除二叉树;二叉排序树：二叉排序树：一种特殊的二叉树，其特点是：左子树上所有结点一种特殊的二叉树，其特点是：左子树上所有结点的值均小于其双亲结点的值，右子树上所有结点的值均大于或等于其的值均小于其双亲结点的值，右子树上所有结点的值均大于或等于其双亲结点的值。双亲结点的值。二叉排序树类的成员函数二叉排序树类的成员函数template void BinTree:insertNode(Node*&t,T val)if(t=NULL)t=new Node(val);else if(valdata)insertNode(t-lchild,val);else inse

14、rtNode(t-rchild,val);template void BinTree:PreOrder(Node*t)if(t!=NULL)coutdatalchild);/先序遍历左子树 PreOrder(t-rchild);/先序遍历右子树 template void BinTree:InOrder(Node*t)if(t!=NULL)InOrder(t-lchild);/中序遍历左子树 coutdatarchild);/中序遍历右子树 template void BinTree:PostOrder(Node*t)if(t!=NULL)PostOrder(t-lchild);/后序遍历左子

15、树 PostOrder(t-rchild);/后序遍历右子树树、森林与二叉树的转换树、森林与二叉树的转换 将树转换成二叉树将树转换成二叉树：在所有的兄弟之间加一条连线；在所有的兄弟之间加一条连线；对每个结点，除了保留与最左边子女的连线外，去掉与其他子女连线；对每个结点，除了保留与最左边子女的连线外，去掉与其他子女连线；将保留下来的边作为左子树的边，兄弟间的连线作为右子树的边。将保留下来的边作为左子树的边，兄弟间的连线作为右子树的边。将一个森林转换成二叉树：将一个森林转换成二叉树：先将森林中的每一棵树变为二叉树，然后将各二叉树的根结点看成兄弟，先将森林中的每一棵树变为二叉树，然后将各二叉树的根结

16、点看成兄弟，用线把它们连到一起，经整理后可得到相应的二叉树。用线把它们连到一起，经整理后可得到相应的二叉树。树、森林到二叉树的转换树、森林到二叉树的转换树、森林与二叉树的转换树、森林与二叉树的转换（续）（续）若结点是其双亲的左子女，则把的右子女、右子女的右子女若结点是其双亲的左子女，则把的右子女、右子女的右子女都都与连线，最后去掉所有双亲到右子女的连线。与连线，最后去掉所有双亲到右子女的连线。2二叉树到树、森林的转换二叉树到树、森林的转换 哈夫曼树基本概念哈夫曼树基本概念 扩充二叉树和带权路径长度：扩充二叉树和带权路径长度：假设假设W0，W1，Wn-1是个实数的集合，其中是个实数的集合，其中W

17、i（-）。若是一棵有个叶结点的二叉树，而且将）。若是一棵有个叶结点的二叉树，而且将W0，W1，Wn-1分别赋给的分别赋给的个叶结点作为它们的权，则称是权值为个叶结点作为它们的权，则称是权值为W0，W1，Wn-1的的扩充二叉树扩充二叉树。带有权。带有权值的叶结点叫做扩充二叉树的值的叶结点叫做扩充二叉树的外结点外结点，其余的分支结点叫做，其余的分支结点叫做内结点内结点。一个有个外结点的扩充二叉树的一个有个外结点的扩充二叉树的带权路径长度带权路径长度（）为：（）为：WPL=其中，其中，Wi为外结点所带的权值；为外结点所带的权值；li为从根结点到外结点的路径长度。为从根结点到外结点的路径长度。inil

18、10iW(a)WPL=40 (b)WPL=50(c)WPL=38 哈夫曼树基本概念哈夫曼树基本概念（续）（续）2最优二叉树最优二叉树通常，把权值取为通常，把权值取为W0，W1，Wn-1的所有扩充二叉树中为的所有扩充二叉树中为最小的扩充二叉树称为最小的扩充二叉树称为最优二叉树最优二叉树。3哈夫曼树哈夫曼树利用哈夫曼提出的方法构造出的最优二叉树称为利用哈夫曼提出的方法构造出的最优二叉树称为哈夫曼树哈夫曼树。4哈夫曼树构造方法哈夫曼树构造方法由给定的个权值由给定的个权值W0，W1，Wn-1构造含有棵扩充二叉树的构造含有棵扩充二叉树的森林，森林中的每棵二叉树都只有一个根结点，且每个根结点都取一个各不相

19、同森林，森林中的每棵二叉树都只有一个根结点，且每个根结点都取一个各不相同的的Wi作为权值；作为权值；用森林中根结点的权值为最小和次小的两棵二叉树作为左、右子树构用森林中根结点的权值为最小和次小的两棵二叉树作为左、右子树构造出一棵新的二叉树，并将新二叉树的根结点的权值取为左、右子树根结点权值之造出一棵新的二叉树，并将新二叉树的根结点的权值取为左、右子树根结点权值之和；和；从森林中删去作为新二叉树左、右子树的两棵二叉树，将新构造的二从森林中删去作为新二叉树左、右子树的两棵二叉树，将新构造的二叉树加入到森林中；叉树加入到森林中；重复步骤重复步骤和和，直到中仅剩下一棵二叉树为止。，直到中仅剩下一棵二叉

20、树为止。哈夫曼树的构造哈夫曼树的构造 哈夫曼树的应用哈夫曼树的应用例例 设电文字符集为设电文字符集为a，b，c，d，e，f，各字符发送频率是，各字符发送频率是6，2，3，3，4，9，利用哈夫曼树构造个字符的编码。利用哈夫曼树构造个字符的编码。以字符发送频率为权值构造哈夫曼树以字符发送频率为权值构造哈夫曼树哈夫曼编码哈夫曼编码各字符的哈夫曼编码是各字符的哈夫曼编码是 a：01 b：001 c：001 d：100 e：101 f：100图的概念图的概念图的定义图的定义 图用二重组（，）表示。其中，是顶点的有穷非空集合；是图用二重组（，）表示。其中，是顶点的有穷非空集合；是中顶点偶对（称为边）的有穷

21、集合。中顶点偶对（称为边）的有穷集合。对一个给定的图，用（）表示对一个给定的图，用（）表示顶点集顶点集，用（）表示，用（）表示边集边集。有向图有向图 如果一个图中的每条边都有方如果一个图中的每条边都有方向，称它为向，称它为有向图有向图。在有向图中，一。在有向图中，一条有向边是由两个顶点组成的有序对。条有向边是由两个顶点组成的有序对。有序对常用尖括号表示，有序对常用尖括号表示，例如，例如，表示一条有向边表示一条有向边，Vi是边的始点，是边的始点，Vj是边的终点。是边的终点。和和表示的是两条不同的表示的是两条不同的边。边。无向图无向图如果一个图中每条边都是没有如果一个图中每条边都是没有方向的，则称

22、此图为方向的，则称此图为无向图无向图。无向图。无向图中组成边的两个顶点是无序的，通常用中组成边的两个顶点是无序的，通常用圆括号表示。圆括号表示。例如，例如，(Vi,Vj)表示一条无向边。表示一条无向边。(Vi,Vj)和和(Vj,Vi)表示的是同一条边。表示的是同一条边。图的常用术语图的常用术语 邻接顶点邻接顶点 在无向图中，若（，）是图中的一条边，则称顶点和互为邻在无向图中，若（，）是图中的一条边，则称顶点和互为邻接顶点。在有向图中，若，是图中的一条边，则称顶点邻接到顶点，接顶点。在有向图中，若，是图中的一条边，则称顶点邻接到顶点，顶点邻接自顶点。顶点邻接自顶点。顶点的度顶点的度 与顶点相关联

23、的边的数目叫做与顶点相关联的边的数目叫做度度。有向图顶点的度还有入度与出度之。有向图顶点的度还有入度与出度之分：顶点的分：顶点的入度入度即以该顶点为终点的边的数目；顶点的即以该顶点为终点的边的数目；顶点的出度出度即以该顶点为始点的边即以该顶点为始点的边的数目。的数目。子图子图 设有两个图（，）、设有两个图（，）、（，）。若）。若VV、EE，并且，并且中的边所关联的顶点都在中的边所关联的顶点都在中，则称图中，则称图是图的是图的子图子图。图的常用术语（续）图的常用术语（续）权权 有些图的边附带有数据信息，称这些数据信息为有些图的边附带有数据信息，称这些数据信息为权权。常把带权的图称为。常把带权的图

24、称为网络网络。路径路径 在图在图G=(V,E)中，若存在顶点序列中，若存在顶点序列VP,Vi1,Vi2,Vin,Vq使得使得(VP,Vi1),(Vi1,Vi2),(Vin,Vq)都在中，则称从顶点都在中，则称从顶点VP到到Vq存在一条存在一条路径路径。路径长度路径长度 对于不带权的图，对于不带权的图，路径长度路径长度是指路径上边的数目；对带权的图，路径是指路径上边的数目；对带权的图，路径长度是指路径上各条边的权值之和。长度是指路径上各条边的权值之和。简单路径简单路径 如果一条路径上除第一个顶点和最后一个顶点可以相同外，其他顶点如果一条路径上除第一个顶点和最后一个顶点可以相同外，其他顶点都不相同

25、，则称此路径为都不相同，则称此路径为简单路径简单路径。连通图连通图 对无向图（，）而言，如果从顶点对无向图（，）而言，如果从顶点Vi到顶点到顶点Vj有一条路径，则有一条路径，则称称Vi和和Vj是连通的。若（）中任意两个不同的顶点是连通的。若（）中任意两个不同的顶点Vi和和Vj都连通，则称都连通，则称此图为此图为连通图连通图。图的存储结构图的存储结构称称A为为邻接矩阵邻接矩阵。1邻接矩阵法邻接矩阵法设图（，）有（设图（，）有（）个顶点）个顶点 V0，V1，Vn-1，可以用一，可以用一个个nn阶的矩阵阶的矩阵A描述图中边的情况。对于描述图中边的情况。对于A中的每个元素中的每个元素aij满足满足否则

26、或（若0),1EVVVVajijiij（0in-1,0jn-1）图的存储结构图的存储结构性质：性质：对无向图而言，顶点对无向图而言，顶点Vi的度数的度数di是矩阵第是矩阵第i行元素值之和，即行元素值之和，即 ；对有向图而言，顶点对有向图而言，顶点Vi的出度为第行元素值之和，顶点的出度为第行元素值之和，顶点Vi的入度为第列的入度为第列元素值之和。顶点元素值之和。顶点Vi的度为的度为1邻接矩阵法（续）邻接矩阵法（续）对于带权的图，邻接矩阵对于带权的图，邻接矩阵A中的元素可以定义为中的元素可以定义为：（0in-1,0jn-1）jijiEVVVVjiWajijiijij否则，但否则，但或（，且若0),

27、10njijiad1010njjinjijiaad图的存储结构图的存储结构2邻接表法邻接表法 用邻接表表示有个顶点的无向图时，需要一个以顺序方式或链接方式存用邻接表表示有个顶点的无向图时，需要一个以顺序方式或链接方式存储的顶点表和个单链表。储的顶点表和个单链表。顶点表的每个表目包括两个域：一个域用来存放顶点顶点表的每个表目包括两个域：一个域用来存放顶点Vi的信息，另一个域的信息，另一个域用来存放一个指针，它指向与该顶点对应的单链表。用来存放一个指针，它指向与该顶点对应的单链表。与顶点与顶点Vi对应的单链表中的每个结点代表了一个与对应的单链表中的每个结点代表了一个与Vi相邻接的顶点，它包相邻接的

28、顶点，它包括三个域：括三个域：dest、weight和和link。dest域中保存了一个与域中保存了一个与Vi相邻接的顶点的下标；相邻接的顶点的下标；weight域存放相应边的权值（对不带权的图，域存放相应边的权值（对不带权的图，weight域可以省略）；域可以省略）；link域保存指域保存指向链表中下一个结点的指针。向链表中下一个结点的指针。图的存储结构图的存储结构2邻接表法邻接表法（续）（续）有向图的邻接表在构造与顶点有向图的邻接表在构造与顶点Vi相关的链表时只链入以相关的链表时只链入以Vi为起点的所有有向为起点的所有有向边，称这种邻接表为边，称这种邻接表为出边表出边表。在顶点在顶点Vi的

29、边链表中链接所有以的边链表中链接所有以Vi为终点的边，称这种链表为为终点的边，称这种链表为入边表入边表。性质：性质：从有向图的出边表中统计从有向图的出边表中统计Vi的边链表中结点个数即可得顶点的边链表中结点个数即可得顶点Vi的出度。的出度。从有向图的从有向图的入边表入边表中统计中统计Vi的边链表中结点个数即可得顶点的边链表中结点个数即可得顶点Vi的入度。的入度。比较：比较：在在邻接矩阵邻接矩阵表示法中表示法中占用的存储单元个数与图中边的数目无关，只与图中占用的存储单元个数与图中边的数目无关，只与图中顶点的个数有关。在邻接表表示法中，需要使用的存储单元不仅与图中顶顶点的个数有关。在邻接表表示法中

30、，需要使用的存储单元不仅与图中顶点的个数有关，而且与边数也有关。点的个数有关，而且与边数也有关。图的遍历图的遍历 深度优先遍历序列：、深度优先遍历序列：、广度优先遍历序列：、广度优先遍历序列：、深度优先搜索遍历深度优先搜索遍历从图中的一个顶点从图中的一个顶点V为起点并访问之，然后访问与相邻接但至今未被访问为起点并访问之，然后访问与相邻接但至今未被访问过的顶点，再访问与邻接但未被访问过的任意一个顶点，依此类推。过的顶点，再访问与邻接但未被访问过的任意一个顶点，依此类推。当到达一个所有邻接顶点都被访问过的顶点时，从已经被访问过的顶点序当到达一个所有邻接顶点都被访问过的顶点时，从已经被访问过的顶点序

31、列中最后一个还有未被访问过的邻接顶点的顶点开始，重复上述遍历过程。列中最后一个还有未被访问过的邻接顶点的顶点开始，重复上述遍历过程。广度优先搜索遍历广度优先搜索遍历任意指定图中的一个顶点，访问此顶点，然后访问与顶点邻接的全部任意指定图中的一个顶点，访问此顶点，然后访问与顶点邻接的全部顶点顶点W1、2、b，再依次访问与，再依次访问与W1、2、b相邻的但未被访问相邻的但未被访问过的顶点，如此下去。过的顶点，如此下去。图的生成树和最小生成树图的生成树和最小生成树 图的生成树图的生成树对连通的无向图、强连通的有向图或有根的有向图，从其中任何一个顶点对连通的无向图、强连通的有向图或有根的有向图，从其中任

32、何一个顶点或根出发都可以不间断地访问到图中的全部顶点。由图的所有顶点加上遍历过程中或根出发都可以不间断地访问到图中的全部顶点。由图的所有顶点加上遍历过程中所经过的边构成的子图称为图的所经过的边构成的子图称为图的生成树生成树。有有n个顶点的生成树必有个顶点的生成树必有n-1条边。条边。图的生成树不是惟一的。图的生成树不是惟一的。最小生成树最小生成树图的各个生成树中各边权值之和为最小的生成树称为图的图的各个生成树中各边权值之和为最小的生成树称为图的最小生成树最小生成树。图的最小生成树图的最小生成树 普里姆算法普里姆算法:从任意一个顶点开始，首先把这个顶点包括在生成树里，然后在一个顶点从任意一个顶点

33、开始，首先把这个顶点包括在生成树里，然后在一个顶点已在生成树里而另一个顶点还未在生成树里的边中找出权值最小的一条边，并把这已在生成树里而另一个顶点还未在生成树里的边中找出权值最小的一条边，并把这条边和其不在生成树里的那个顶点包括进生成树，如此进行下去直到把所有的顶点条边和其不在生成树里的那个顶点包括进生成树，如此进行下去直到把所有的顶点都包括进生成树。都包括进生成树。最小生成树不是惟一的。最小生成树不是惟一的。图的最短路径图的最短路径 最短路径最短路径:在带权的有向图中求两个顶点间长度最短的路径问题。在带权的有向图中求两个顶点间长度最短的路径问题。两种情况：一是求从一个顶点到其他各顶点的最短路

34、径；两种情况：一是求从一个顶点到其他各顶点的最短路径；二是求每对顶点之间的最短路径。二是求每对顶点之间的最短路径。03030350201502051504510500A的最短路径到尚未找到从的最短路径到已找到从iiVVVVis0001AOV网和拓扑排序网和拓扑排序AOV网网:在有向图中，用顶点表示活动，用有向边表示活动之间的先后关系。称这在有向图中，用顶点表示活动，用有向边表示活动之间的先后关系。称这样有向图为用顶点表示活动的网络，简称样有向图为用顶点表示活动的网络，简称AOV网网(Activity On Vertices)。拓扑序列和拓扑排序：拓扑序列和拓扑排序：将一个将一个AOV网所有顶点

35、排成一个线性序列，并使该序列满足以下条件：网所有顶点排成一个线性序列，并使该序列满足以下条件：若在网中有一条从顶点若在网中有一条从顶点i到到j的路径，则在序列中顶点的路径，则在序列中顶点i必在顶点必在顶点j的前的前面。满足此条件的面。满足此条件的AOV网的顶称点序列称为网的顶称点序列称为拓扑序列拓扑序列，称构造拓扑序列的过程，称构造拓扑序列的过程为为拓扑排序拓扑排序。拓扑排序拓扑排序拓扑排序算法：拓扑排序算法：从网中选择一个入度为的顶点并输出之；如果找不到入度为从网中选择一个入度为的顶点并输出之；如果找不到入度为的顶点，则说明此的顶点，则说明此AOV网存在回路，不能得到拓扑序列。网存在回路，不

36、能得到拓扑序列。从网中删除该顶点和所有以它为始点的边。从网中删除该顶点和所有以它为始点的边。重复步骤重复步骤、，直到，直到AOV网中的全部顶点均已输出。网中的全部顶点均已输出。存在回路的存在回路的AOV网不能得到拓扑序列。网不能得到拓扑序列。一个一个AOV网的拓扑序列不是惟一的。网的拓扑序列不是惟一的。序列之一：序列之一：c0 c1 c2 c4 c3 c7 c8 c6 c5序列之二：序列之二：c0 c7 c8 c1 c4 c2 c3 c5 c6关键路径关键路径 AOE网：网：在带权的有向图中，用顶点表示事件，边表示活动，权表示活动的持续时在带权的有向图中，用顶点表示事件，边表示活动，权表示活动

37、的持续时间，称此图为间，称此图为AOE网网。AOE网应该是无环的，且存在惟一的入度为的顶点（称为网应该是无环的，且存在惟一的入度为的顶点（称为源点源点）和惟）和惟一的出度为的顶点（称为一的出度为的顶点（称为汇点汇点）。）。在在AOE网中，有些活动可以并行执行，完成整个工程所需要的最少时间由网中，有些活动可以并行执行，完成整个工程所需要的最少时间由从源点到汇点的最长路径的长度决定，称具有最大长度的路径为从源点到汇点的最长路径的长度决定，称具有最大长度的路径为关键路径关键路径。关键路径上的活动称为关键路径上的活动称为关键活动关键活动。拓扑排序拓扑排序关键路径的相关量：关键路径的相关量：活动活动ai的的最早开始时间最早开始时间用用ei表示。活动表示。活动ai的的最迟开始时间最迟开始时间用用li表示表示。li与与ei之差为完成活动之差为完成活动ai的时间余量。的时间余量。若某个活动若某个活动ai有有li=ei，则称活动，则称活动ai是一个是一个关键活动关键活动。最早发生时间和最迟发生时间的计算：最早发生时间和最迟发生时间的计算：从从ee0=0开始向汇点递推，即开始向汇点递推，即 (k=1,2,.,n-1)从从len-1=een-1开始向源点递推，即开始向源点递推，即 (j=n-2,.,0)max,jkjPVVkweeeekjmax,jkkSVVjwlelekj