7.17.3（与第9章作业合交）

1、1具体内容：先生成一棵二叉树，再用中序遍历方式打印每具体内容：先生成一棵二叉树，再用中序遍历方式打印每个结点值，并统计其叶子结点的个数个结点值，并统计其叶子结点的个数。具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫曼编码。夫曼编码。具体内容：参见严题集具体内容：参见严题集P149 实习实习5.2要求，或参见自测卷要求，或参见自测卷27.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的其他运算图的其他运算7.5 7.5 图的应用图的应用37.4 7.4 图的其他运算图的其他运算

2、1. 求图的生成树求图的生成树2. 求最小生成树求最小生成树3. 求最短路径求最短路径4. 求关节点和重连通分量（略）求关节点和重连通分量（略）5. 拓扑排序（拓扑排序（见下节见下节）6. 求关键路径（求关键路径（见下节见下节）41. 求图的生成树求图的生成树（小结）（小结）生成树的特征生成树的特征: :n n 个顶点的个顶点的连通图连通图的生成树有的生成树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。求生成树的方法求生成树的方法: :DFSDFS（深度优先搜索）（深度优先搜索）BFSBFS（广度优先搜索）（广度优先搜索）注注1 1：生成树是原图的生成树是原图的极小极小连通子图；连通

3、子图；注注2 2：从不同顶点出发进行从不同顶点出发进行DFSDFS或或BFSBFS，得到的，得到的生成树不同，即：图的生成树不惟一。生成树不同，即：图的生成树不惟一。5例例1 ：画出下图的生成树：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4无向连通图无向连通图v0v1v2v4v4v3v0v1v2v4v4v3本例无回溯本例无回溯6Minimum Cost Spanning Tree2.2.求最小生成树求最小生成树目标：目标：在网（有权图）的多个生成树中，寻找一在

4、网（有权图）的多个生成树中，寻找一个个各边权值之和最小各边权值之和最小的生成树（的生成树（MSTMST）。）。典型实例：典型实例： n n个城市建网，如何选择个城市建网，如何选择n1n1条线路，使总费条线路，使总费用最少？用最少？用最小生成树求解用最小生成树求解v Kruskal（克鲁斯卡尔克鲁斯卡尔）算法）算法v Prim（普里姆普里姆）算法）算法 求最小生成树有两种方法：求最小生成树有两种方法：注：任何一个无向连通图的最小生成树只有一棵。注：任何一个无向连通图的最小生成树只有一棵。对边操作对边操作对顶点操作对顶点操作7KruskalKruskal算法效率分析：算法效率分析：KruskalK

5、ruskal算法的时间效率算法的时间效率O O（elogelog2 2e e）KruskalKruskal算法算法是归并边，适用于稀疏图是归并边，适用于稀疏图（用邻接表）（用邻接表）8PrimPrim算法效率分析：算法效率分析：PrimPrim算法的时间效率算法的时间效率O O（n n2 2）PrimPrim算法算法是归并顶点，适用于稠密网。是归并顶点，适用于稠密网。9一顶点到其一顶点到其余各顶点余各顶点3. 3. 求最短路径求最短路径两种常见的最短路径问题：两种常见的最短路径问题：一、一、 单源最短路径单源最短路径用用Dijkstra（迪杰斯特拉）（迪杰斯特拉）算法算法二、所有顶点间的最短路

6、径二、所有顶点间的最短路径用用Floyd（弗洛伊德）（弗洛伊德）算法算法典型用途：典型用途：交通问题。如：城市交通问题。如：城市A A到城市到城市B B有多条线路，但每条有多条线路，但每条线路的交通费（或所需时间）不同，那么，线路的交通费（或所需时间）不同，那么，如何选择一条线路，如何选择一条线路，使总费用（或总时间）最少？使总费用（或总时间）最少？问题抽象：问题抽象：在在带权有向图带权有向图中中A A点（源点）到达点（源点）到达B B点（终点）的多点（终点）的多条路径中，寻找一条条路径中，寻找一条各边权值之和最小各边权值之和最小的路径，即最短路径。的路径，即最短路径。（注：最短路径与最小生成

7、树不同，路径上不一定包含（注：最短路径与最小生成树不同，路径上不一定包含n n个顶点）个顶点）任意两顶任意两顶点之间点之间10一、单源最短路径一、单源最短路径 ( (Dijkstra算法算法) )目的：目的： 设一有向图设一有向图G=G=（V, EV, E），已知各边的权值，以某），已知各边的权值，以某指定点指定点v v0 0为源点，求从为源点，求从v v0 0到图的其余各点的最短路径。到图的其余各点的最短路径。限定限定各边上的权值大于或等于各边上的权值大于或等于0 0。例例1 1：源点源点从从FAFA的路径有的路径有4 4条：条： FAFA： 2424 FBA FBA： 5 518=2318

8、=23 FBCA FBCA：5+7+9=215+7+9=21 FDCAFDCA：25+12+9=3625+12+9=36想一想：想一想：从从FBFB的最短路径是哪条？的最短路径是哪条？从从FCFC的最短路径是哪条？的最短路径是哪条？迪杰斯特拉迪杰斯特拉应按路径应按路径“长度长度” ” 递增的次序，逐步产生最短路径递增的次序，逐步产生最短路径11可以可以通过调用通过调用n n次次DijkstraDijkstra算法算法来完成，来完成，时间复杂度为时间复杂度为O(nO(n3 3) )还有更简单的一个算法：还有更简单的一个算法：FloydFloyd算法算法（略）（略）127.5 图的应用图的应用 A

9、OV网网(Activity On Vertices)用用顶点顶点表示活动的网络表示活动的网络AOVAOV网定义：网定义：若用有向图表示一个工程，在图若用有向图表示一个工程，在图中用顶点表示活中用顶点表示活动，用弧表示活动间的优先关系动，用弧表示活动间的优先关系。Vi 必须先于活动必须先于活动Vj 进行进行。则这样的有向图叫做则这样的有向图叫做用顶点表示活动的网络用顶点表示活动的网络，简称，简称 AOV。 AOE网网(Activity On Edges)用用边边表示活动的网络表示活动的网络AOEAOE网定义网定义：在带权有向无环网中，：在带权有向无环网中， 用有向边表示一个工程中用有向边表示一个

10、工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图叫做则这样的有向图叫做用边表示活动的网络用边表示活动的网络，简称，简称 AOE有两种常用的活动网络（有两种常用的活动网络（ Activity Network）：）：13常用于大型工程的计划管理。常用于大型工程的计划管理。利用利用AOE网络可网络可以解决以下两个问题：以解决以下两个问题： 14（1）列出所有的）列出所有的关键路径关键路径；（2）完成整个工程）完成整个工程至少至少需要多少时间？需要多少时间？（3）事件）事件V5 的最早的最早完成完成时间是多少？时间是多少？（4

11、）活动）活动 a6 的的最早最早开工时间是多少？开工时间是多少？1. 【计算机系考研题计算机系考研题1999】对于下面的对于下面的AOE网络，试回答下列问题：网络，试回答下列问题： （8分）分）15刘先刘先 “蒙蒙”答有关内容：答有关内容： （1） 列出所有的关键路径；列出所有的关键路径； 答：答：关键路径即为关键路径即为最长路径最长路径。从图中大致能看出的最长路径有：。从图中大致能看出的最长路径有：（2）完成整个工程至少需要多少时间？）完成整个工程至少需要多少时间？答：应该就是关键路径消耗的时间，应当是答：应该就是关键路径消耗的时间，应当是。 （3）事件）事件V5 的最早完成时间是多少？的最

12、早完成时间是多少？答：这应该是答：这应该是V1-V5之间的关键路径问题。之间的关键路径问题。若以若以V5的开始时间计，则：的开始时间计，则：-510+12（4）活动）活动a6的最早开工时间是多少？的最早开工时间是多少？答：这仍应该是答：这仍应该是V1-V6（因为（因为a6是由事件是由事件V6产生的）之间的产生的）之间的关键路径问题：关键路径问题：（510+8）（53天）天） （53天）天）（但是否全部关键路径已经找出？没把握！）（但是否全部关键路径已经找出？没把握！）16a2=10a1(5)+a2(10)+a7(8)+a6(12)+a12(6)+a13(12)=53(天）天）171819图图存储结构