课件七图.ppt

数据结构课程的内容 DFS 算法效率分析: 2. 图的生成树和生成森林 例：n个城市之间建立通讯网络 要求 n个城市中任意两个城市可通讯 最省经费 如何选n-1条 连通 线路最短（最经济） 包括n个城市 连通网 n个城市为顶点 边上设置线路相应的代价 具体示例： 实验一问题： 部分同学在算法中设置全局变量，保存链表的长度，想法很好，做的很好； 实验报告中，应该有：核心算法设计、有主要流图、有程序运行效果的截图、有程序调试分析、有主要代码，部分同学写的全，部分写的不全； 数据的读入：不要多行读入，一行全部读进去 char c; cinc; //一行读入，读入多个单字符有效 读入带空格的字符：char buf[20]; scanf(“s%”,buf); //或者gets(buf); 读入一行整数：scanf(%d,%d,p1-num,p1-key) 例1： 对各最短路径按路径长度递增排列 可以证明V0到其余各顶点Vk的最短路径长度，或是从V0到Vk的直接路径的权值；或是从V0经顶点vi（vi是指已求得的最短路径长度的顶点或顶点序列）到Vk的路径权值之和 迪杰斯特拉(Dijkstra)算法思想 求最短路径步骤： 具体算法： 189页 算法7.15 方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次—— T(n)=O(n3) 方法二：弗洛伊德(Floyd)算法 算法思想：逐个顶点试探法 算法实现 图用邻接矩阵存储 length[][]存放最短路径长度 path[i][j]是从Vi到Vj的最短路径上Vj前一顶点序号 见图：192页 具体算法：191页 作业： 7.11 7.13 拓扑排序的算法实现 拓扑排序的算法实现（续） 算法实现 求各顶点的入度indegree[0… vexnum-1] 初始化栈 把邻接表中所有入度为0的顶点进栈。 栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈。 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。 算法演示示例 定义几个与计算关键活动有关的量： ① 事件Vi 的最早可能开始时间Ve(i) 是从源点V1 到顶点Vi 的最长路径长度 如V5 ② 事件Vi 的最迟允许开始时间Vl[i] 是在保证汇点Vn 在Ve[n] 时刻完成的前提下，事件Vi 的允许的最迟开始时间 ③ 活动ak 的最早可能开始时间 e[k] eg. a5 设活动ak 在边 Vi , Vj 上, 则e[k]是从源点V1到顶点Vi 的最长路径长度。因此, e[k] = Ve[i] ④ 活动ak 的最迟允许开始时间 l[k] 假设ak 在边 Vi , Vj 上 l[k]是在不会引起时间延误的前提下, 该活动允许的最迟开始时间 l[k] = Vl[j] - dut(i, j) 其中, dut(i, j)是完成 ak 所需的时间 ⑤ 时间余量 l[k] - e[k] 表示活动 ak 的最早可能开始时间和最迟允许开始时间的时间余量。l[k] == e[k] 表示活动 ak 是没有时间余量的关键活动。 为找出关键活动, 需要求各个活动的 e[k] 与 l[k]，以判别是否 l[k] == e[k] 问题分析 如何找e(i)=l(i)的关键活动ai？ 求关键路径步骤 求Ve(i) 从源点V1 到顶点Vi的最长路径长度 求Vl(i) 求e(i)（=Ve(i)） 求l(i)（（Vl(j)-dut(i,j)） 计算l(i)-e(i) 本章小结 6.14 找出所有满足下列条件的二叉树 (1) 它们在先序和中序遍历时，得到的结点访问序列相同； -----只有根 或每个结点只含右子树 (2) 它们在后序和中序遍历时，得到的结点访问序列相同； -----只有根 或每个结点只含左子树 (3)