数据结构图结构.ppt

一. AOV网络 用途：我们经常用有向图来描述一个工程或系统的进行过程。一般来说，一个工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成。 例：AOV网络若用于教学计划的制定，可以解决： 哪些课程是必须先修的，哪些课程是可以并行学习的。 预备知识：拓扑排序 什么叫拓扑排序？ ——对一个有向无环图中的顶点排成一个具有前后次序的线性序列。 课程编号 课程名称 先决条件 C1 程序设计基础 无 C2 离散数学 C1 C3 数据结构 C1,C2 C4 汇编语言 C1 C5 语言的设计和分析 C3,C4 C6 计算机原理 C11 课程编号 课程名称 先决条件 C7 编译原理 C5,C3 C8 操作系统 C3,C6 C9 高等数学 无 C10 线性代数 C9 C11 普通物理 C9 C12 数值分析 C9,C10,C1 C1 C4 C2 C3 C5 C9 C7 C12 C10 C11 C6 C8 例： 进行拓扑排序的方法： 输入AOV网络。令 n 为顶点个数。 在AOV网络中选一个没有直接前驱的顶点, 并输出之; 从图中删去该顶点, 同时删去所有它发出的有向边; 重复以上 2、3 步, 直到： 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或： 图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。 拓扑排序算法：重复选择没有直接前驱的顶点。 V1 V2 V4 V3 V6 V5 (1) V1 V2 V4 V3 V5 (2) V2 V4 V3 V5 (3) V2 V3 V5 (4) V2 V5 (5) V2 (6) 例： 二. AOE网络 用途：常用于大型工程的计划管理。利用AOE网络可以 解决以下两个问题： (1) 完成整个工程至少需要多少时间(假设网络中没有环)? (2) 为缩短完成工程所需的时间, 应当加快哪些活动? 或者说，哪些活动是影响工程进度的关键？ 预备知识：关键路径 问题1：由于在AOE—网中有些活动可以并行地进行，故完成工程的最短时间是从开始点到完成点的最长路径的长度，即关键路径的长度。 基本术语： 1.源点：入度为零的点（工程的开始点，只有一个）。 汇点：出度为零的点（工程的完成点，只有一个）。 2.路径长度:指路径上各活动持续时间之和， 不是路径上弧的数目。 3.关键路径：路径长度最长的路径。 关键活动：满足l(s) = e(s)的活动as 。 4. 活动as的最早开始时间e(s)： 若该活动在弧<vi,vj>上，则: 活动as的最迟开始时间l(s)： 在不推迟整个工程完成的前提下，该活动最迟 必须开始进行的时间。 e(s) = Ve(i) l(s) = Vl(j) — dut (as) 5.事件vi的最早发生时间Ve(i)： 从开始点V1到Vi的最长路径长度。 求法： 从ve(0)=0开始向前递推 6.事件vi的最迟发生时间Vl(i)： 求法：从vl(n-1)=ve(n-1)起向后递推 ve(j) = Max { ve(i)+dut(<i,j>) } <i,j>∈T 注：T是所有以第j个顶点为头的弧的集合。 vl(i) = Min {vl(j)-dut(<i,j>)} <i,j> ∈S 注：S是所有以第i个顶点为尾的弧的集合。 问题2: 因为关键路径上的所有活动都是关键活动，所 以提前完成非关键活动并不能加快工程的进度。 要在最短时间内完成一项工程，需要做以下工作： 1. 画出该工程各个子工程的有向无环网络； 2. 求出各个顶点（即事件）的ve和vl并找到关键路径； 3. 根据各顶点的ve和vl值，求出每条弧s上活动的e(s) 和l(s)，由此找到关键活动。 举例：P186 图7.30_7.31 实现：P184_185 a2 = 2 a3 = 2 a4 = 3 a5 = 4 a1 = 3 a6 = 3 a7 = 2 a8 = 1 V1 V2 V3 V4 V5 V6 V1 V3 V4 V6 a2 a5 a7 顶点 ve vl v1 0 v2 v3 v4 v5 v6 3 2 6 6 8 4 2 6 7 8 活动 e l l-e a1 a2 a3 a4 a5 a6 a7 a8 0 3 3 2 2 6 6 1 0 4 4 2 5 6 7 1 0 1 1 0 3 0 1 0 举例： 0 图 存储结构 遍 历 邻接矩阵 邻 接 表 十字链表 邻接多重表 深度优先搜