有向无环图及应用.ppt

《有向无环图及应用.ppt》由会员分享，可在线阅读，更多相关《有向无环图及应用.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7.5 有向无环图及应用 7.5.1 拓扑排序 用顶点边表示活动的网络，简称用顶点边表示活动的网络，简称 AOV AOV网络网络(Activity On Vertices)(Activity On Vertices)顶点顶点：一个工程中的活动：一个工程中的活动(Activity)(Activity)边：活动的顶点间的优先关系边：活动的顶点间的优先关系(Relation)(Relation)要解决的问题是：要解决的问题是：将各个顶点将各个顶点（代表各个活动）排列成一个线性有序（代表各个活动）排列成一个线性有序的序列，使得的序列，使得AOVAOV网络中所有应存在的前驱和后继关系网络中所有应存在的前

2、驱和后继关系都能得到满足。都能得到满足。课程代号 课程代号 课程名 课程名 先修课程 先修课程 C C1 1 高等数学 高等数学 C C2 2 程序设计基础 程序设计基础 C C3 3 离散数学 离散数学 C C1 1,C,C2 2 C C4 4 数据结构 数据结构 C C3 3,C,C2 2 C C5 5 高级语言程序设计 高级语言程序设计 C C2 2 C C6 6 编译方法 编译方法 C C5 5,C,C4 4 C C7 7 操作系统 操作系统 C C4 4,C,C9 9 C C8 8 普通物理 普通物理 C C1 1 C C9 9 计算机原理 计算机原理 C C8 8 n n可以用可以

3、用有向图有向图表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，用顶用顶点表示活动点表示活动。有向边有向边表示：表示：VVi i 必须先于活动必须先于活动VVjj 进行。这种有向图叫做顶点表示活动的进行。这种有向图叫做顶点表示活动的AOVAOV网络网络(Activity On Vertices)(Activity On Vertices)。n n在在AOVAOV网络中，如果活动网络中，如果活动VVi i 必须在活动必须在活动VVj j 之前进行，之前进行，则存在有向边则存在有向边，AOV AOV网络中不能出现有向回网络中不能出现有向回路，即有向环。在路，即有向环。在AOVAOV网络中

4、如果出现了有向环，则网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。意味着某项活动应以自己作为先决条件。n n因此，对给定的因此，对给定的AOVAOV网络，必须先判断它是否存在有网络，必须先判断它是否存在有向环。向环。一、什么是拓扑排序一、什么是拓扑排序 将各个顶点将各个顶点(代表各个活动代表各个活动)排列成一个线性有序的排列成一个线性有序的序列，使得序列，使得AOVAOV网络中所有应存在的前驱和后继关系都网络中所有应存在的前驱和后继关系都能得到满足。能得到满足。这种这种构造构造AOVAOV网络全部顶点的拓扑有序序列的运算网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。就叫做拓扑排序。例如，对学生选课工程图进行拓扑排序，得到的拓例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为扑有序序列为 C C11,C,C22,C,C33,C,C44,C,C55,C,C66,C,C88,C,C99,C,C77或或 CC11,C,C88,C,C99,C,C2 2,C,C55,C,C3 3,C,C44,C,C77,C,C66