终点从V0到各终点的弧值和最短路径V1V2V3V4V5Vj10V0V2.PPTVIP

预习内容和重点 拓扑排序（能说出拓扑排序的算法思想、能根据要求写出拓扑排序的序列、理解拓扑排序的算法实现） 关键路径（相关概念、掌握关键路径的算法思想、能求出关键路径） 最短路径（能说出Dijkstra求解最短路径的算法思想、理解Dijkstra求解最短路径的算法实现） 回答问题1 什么是有向无环图(DAG）？下图是不是DAG？有向无环图有何用途？ 回答问题2 假设以有向图表示一个工程的施工图或程序的流程图，则程序中能否出现回路？ 回答问题4 何谓拓扑排序？ 回答问题5 如何进行拓扑排序？ 回答问题6 回答问题7 如何在计算机内实现有向图的拓扑排序？ 回答问题8 对课本中的拓扑排序实现算法还可怎么改变？ 回答问题11 什么是AOV网? 回答问题12 什么是AOE网? 有什么用? 回答问题13 什么是源点、 汇点、 关键路径、 关键活动？ 回答问题15 回答问题16 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小？如下图从顶点V1到V7的最短路径是？ 回答问题17 迪杰斯特拉算法的算法思想是什么？ 回答问题18 如何实现迪杰斯特拉算法？ 下节课学习内容和重点 查找（相关概念、理解各种静态查找表查找方法、掌握顺序表查找、折半查找的实现算法及其性能分析） * * G1 A B C D 如何检查有向图中是否存在回路？ 回答问题3 C8 C3 C5 C4 C9 C6 C7 C1 C2 G1 A B C D V1 V4 V3 V2 V1 V4 V3 V2 换句话说：对有向图进行如下操作，按照有向图给出的次序关系，将图中的顶点排成一个线性序列，对于没有限定次序关系的顶点，则可以人为加上任意的次序关系。 G1 A B C D C8 C3 C5 C4 C9 C6 C7 C1 C2 检测一个有向图是否存在回路的方法：对有向图构造其顶点的拓扑有序序列，若图中所有顶点都在它的拓扑有序序列中，则该图中必定不存在环。 有向图的拓扑有序序列是否唯一？ C8 C3 C5 C4 C9 C6 C7 C1 C2 分析： （1）拓扑排序最关键的操作是什么？ （2）图的存储结构？ （3）如何处理多个入度为0的顶点？ 拓扑排序算法实现 实现拓扑排序的算法基础 存贮结构:假设有向图以邻接表的形式存储 操作过程: 将所有入度为0的顶点入栈； 当栈非空时重复执行下列操作： 从栈中退出顶点k； （1）将k顶点的信息输出； （2）将与k邻接的所有顶点的入度减1。 回答问题9 C0 C1 C2 C3 C4 C5 C0 C1 C2 C3 0 C4 C5 0 degree data adj 1 3 0 1 0 3 1 vex link 3 0 5 1 5 0 0 1 5 0 按照课本中的拓扑排序实现算法，写出下图的拓扑有序序列。 拓扑排序算法的时间复杂度是多少？ 回答问题10 如果给定的有向图有n个顶点和e条边，那么求各顶点入度的时间为O（e），在拓扑排序的过程中，查找入度为零的顶点的时间为O（n），顶点进栈及退栈输出共执行n次，入度减1的操作执行e次，所以，总的执行时间为O（n+e）。 C8 C3 C5 C4 C9 C6 C7 C1 C2 v0 v1 v2 v3 v4 v5 v6 v7 v8 6 4 5 2 1 1 8 7 2 4 4 源点 汇点 6 1 7 4 如何求关键路径？如何求关键活动？ 回答问题14 a4=3 1 2 3 4 5 6 a1=3 a2=2 a5=4 a3=2 a6=3 a7=2 a8=1 V1 0 0 V2 3 4 V3 2 2 V4 6 6 V5 6 7 V6 8 8 a1 0 1 1 a2 0 0 0 a3 3 4 1 a4 3 4 1 a5 2 2 0 a6 2