数据结构课件第7章图2章节幻灯片.ppt

6.5 Dijkstra算法复杂度分析 Dijkstra算法是典型的贪婪算法 Dijkstra算法的时间复杂度是O(n2) Dijkstra算法的空间复杂度是O(n) 4.3.6 普里姆算法样例(结果) lowcost nearvex 0 1 2 3 4 5 6 0 16 12 22 25 10 14 -1 -1 -1 -1 -1 -1 -1 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 原图 边 (1,6,14) 加入生成树 12 5 0 4 6 1 3 2 10 25 14 22 16 12 4.3.7 普里姆算法复杂度分析 分析以上算法, 设连通网络有 n 个顶点, 则该算法的时间复杂度为 O(n2), 它适用于边稠密的网络。 注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。当各边的权值不相同时，产生的生成树是唯一的 4.3.8 最小生成树的另一种求法(并查) 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 28 25 14 24 22 16 18 12 5 0 4 6 1 3 2 28 25 14 24 22 16 18 5 0 4 6 1 3 2 28 25 24 22 16 18 5 0 4 6 1 3 2 28 25 24 22 18 5 0 4 6 1 3 2 28 25 24 18 5. 有向无环图及其应用 5.1 有向无环图概述 5.2 拓扑排序 5.3 关键路径 5.1 有向无环图概述 一个无环的有向图称为有向无环图(directed acycline graph, DAG) 有向树 有向图 用深度优先遍历判断图是否有环 5.2 拓扑排序 5.2.1 偏序和全序 5.2.2 AOV网及其应用 5.2.3 拓扑排序 5.2.1 偏序和全序 偏序：若集合X上的关系R是自反的、反对称的、和传递的，则称R是集合X上的偏序关系（例如，集合包含） 全序：在一个偏序关系中，如果任意两个元素x和y之间必然存在关系xRy或yRx，则称集合上存在全序关系（例如，数轴上点的大小关系） 把全序的关系符号化后，全序关系称为拓扑有序 由偏序关系增加关系约束，得到全序的过程称为拓扑排序 有限集合上的无环偏序一定可以扩展成为全序 5.2.2 AOV网及其应用 5.2.2.1 什么是AOV网 5.2.2.2 学生课程学习工程图 5.2.2.3 拓扑排序的方法描述 5.2.2.4 拓扑排序过程 5.2.2.5 AOV网络及其邻接表表示 5.2.2.6 拓扑排序的算法 5.2.2.1 什么是AOV网 计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了 可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边Vi, Vj表示活动Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络 (Activity On Vertices) 5.2.2.2 学生课程学习工程图 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8 课程代号 课程名称 先修课程 5.2.2.2 学生课程学习工程图(续) C8 C3 C5 C4 C9 C6 C7 C1 C2 5.2.2.3 拓扑排序的方法描述 ① 输入AOV网络。令 n 为顶点个数。 ② 在AOV网络中选一个没有直接前驱的顶点（这样的点一定存在，否则…