数据结构 第七章 图7.2.pptVIP

* * 7.5????? 有向无环图及其应用 一、有向无环图 二、拓扑排序 三、关键路径 一、有向无环图 7.5????? 有向无环图及其应用 有向无环图(directed acycline graph)，简称DAG图，是一个无环的有向图。 有向无环图是描述一项工程或系统的进行过程的有效工具。 对整个工程和系统，人们关心两方面的问题： 工程能否顺利进行--拓扑排序（AOV网）； 估算整个工程完成所必须的最短时间--关键路径(AOE网)； 二、拓扑排序 1.什么是拓扑排序？ 7.5????? 有向无环图及其应用 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 课程代号 课程名称 先修棵 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 无 C1 C1,C2 C1 C3,C4 C11 C3.C5 C3,C6 无 C9 C9 C1,C9,C10 程序设计基础 离散数学 数据结构 汇编语言 语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 例 AOV网(Activity On Vertex Network) 用顶点表示活动，用弧表示活动间的优先关系的有向图称AOV网。 7.5????? 有向无环图及其应用 二、拓扑排序 问题提出：学生选修课程问题 顶点——表示课程 有向弧——表示先决条件，若课程i是j的先决条件，则图中有弧i,j 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序 拓扑排序的定义 所谓拓扑序列，就是把AOV网中的所有顶点排成一个线性序列，该序列满足如下条件：若AOV网中存在弧vi,vj，则在该序列中，vi必位于vj之前。 构造AOV网的拓扑序列的操作被称为拓扑排序。 7.5????? 有向无环图及其应用 二、拓扑排序 a.在有向图中选一个没有前驱(入度为0)的顶点且输出之。 b.从图中删除该顶点及所有以它为尾的弧。 c.重复执行a和b，直到全部顶点均已输出，或者当图中不存在无前驱的顶点为止。 7.5????? 有向无环图及其应用 二、拓扑排序 2.如何进行拓扑排序？ 示例 拓扑序列：v0-v3-v2-v4-v1 7.5????? 有向无环图及其应用 二、拓扑排序 v0-v2-v3-v4-v1 v0-v2-v3-v1-v4 v0-v2-v1-v3-v4 v0-v3-v2-v1-v4 结论：一个AOV网的拓扑序列不是唯一的 a. 采用邻接表作有向图的存储结构，且在头结点增加一 个存放顶点入度的分量(indegree)。 7.5????? 有向无环图及其应用 二、拓扑排序 3. 拓扑排序算法的实现 b. 把邻接表中所有入度为0的顶点进栈 c. 栈非空时，输出栈顶元素Vj并出栈；在邻接表中查 找Vj的直接后继Vk，把Vk的入度减1，即indegree[k]-1； 若Vk的入度为0则进栈。 重复c操作直至栈空为止。 若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。 7.5????? 有向无环图及其应用 二、拓扑排序 算法描述 例 1 2 3 4 5 6 输出序列：6 1 3 2 4 5 0 1 2 2 indegree first 4 4 3 2 ^ ^ ^ adjvex next 3 ^ 1 4 ^ 1 3 0 1 2 3 4 5 6 ^ 0 1 2 3 4 5 邻接表的存储表示 表结点： typedef struct ArcNode { int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置 struct ArcNode *nextarc; //链域，指示下一条边或弧 }ArcNode; adjvex nextarc 头结点： typedef struct VNode { vertextype data; //存放顶点信息 int indegree; //存放顶点的度 ArcNode *firstarc; //指示第一个邻接点 }Vnode,AdjList[MAX_VERTEX_NUM]; data firstarc 邻接表存储结构：typedef struct{ AdjList vertices;