第三章在前面单拓扑的基础上,提出了全拓扑排序算法。该算法对数据结构进行改进,提出了基于层次和邻接表的数据结构,基于层次思想求得所有的拓扑序列。这一章介绍全拓扑排序算法的概念,并通过流程图介绍全拓扑排序算法如何求得所有的拓扑序列。最后给出了全拓扑排序算法的核心代码,并对代码做了些解释,给出了该算法的时间复杂度。
第四章介绍了MFC编程的概念及其算法的实现,给出了系统的功能框架:输入功能、输出功能和决策功能。输入功能包括:顶点的基本信息和决策信息;输出功能包括:有向无环图的绘制,全拓扑序列的输出和决策得到得拓扑序列的输出,决策则实现了某些子工程在安排时有特殊要求时,如何从多个拓扑序列中选择能满足条件的序列。本章最后以实例给出了并行安排子工程的思想,进上步提升了拓扑排序算法的实用价值。
第五章给出了程序对给定5组数据的测试结果,并对全拓扑排序算法的优缺点进行总结,给出了改进的方向。
 第二章  拓扑排序算法研究的现状
2.1 拓扑排序算法的基本概念
2.1.1 定义和术语
拓扑排序算法是在AOV网中求得的顶点的线性序列,首先给出下面几个相关的定义和术语。
(1) AOV网:用顶点表示活动,用弧表示活动间优先关系的有向图,称为顶点表示活动的网,即AOV网。AOV网中的优先关系是一种逆序的关系,即具有传递性和自反性。AOV网是描述一项工程或系统进行过程的有效方法。可以用来表示各种流程图。
(2) 偏序:指集合中只有部分成员可以进行比较。
(3) 全序:指集合中所有成员之间均可以进行比较。
在一个AOV网中,若存在一个顶点i到顶点j的一条有向路径,则顶点i优先于顶点j。显然AOV网中顶点具有偏序关系。
(4) 拓扑排序:有某个集合的一个偏序得到该集合的一个全序的操作。
(5) 拓扑序列:是AOV网中顶点的线性序列,使得对AOV网中任意两个顶点i和j,若在网中i领先于j,则在线性序列中i是j的前驱顶点。
2.1.2 拓扑排序的思想
1 拓扑排序算法的描述
(1)输出入度为零的顶点
    (2)删除该顶点及与之相关联的有向边
重复步骤(1)、(2)。有两种终止的可能:一种可能是所有的顶点全部输出,所得到的序列为拓扑序列;另一种可能是还有顶点没有输出,但是不存在入度为零的顶点,表示该AOV网中存在有向回路,应当重新对实际问题进行分析,得到正确的AOV网,重新求解。
AOV网中,初始时顶点的入度为0(没有前躯顶点),说明该顶点不受任何前驱活动的制约,所以这些顶点可以最先输出。这些顶点输出后,经过第(2)步操作,删除该顶点及与之相关联的有向边,由该活动对其后继活动的制约关系解除,这将使得某些顶点的入度减1,可能产生新的入度为0的顶点,这些在运算过程中入度为0的顶点表示虽然最初顶点所对应的活动受前驱活动制约,但随着前驱活动已安排,它们也成为无制约的活动,因而可以在下面得到安排。这样循环往复,如果AOV网中没有回路,则可以将所有顶点输出,表示所有活动都可以依序正常安排工作;如果AOV网中存在着回路,意着再也找不到入度为0的顶点,算法直接结束,说明该工程的各活动之间的制约关系有错,重新分析问题,重新得到一个可行的AOV网。
算法流程图见图2.1。图 2.1 拓扑排序算法流程图
2  并行拓扑排序算法的基础
根据拓扑排序算法的思想,可以断言一个AOV的顶点所存在的拓扑序列不一定唯一,因为在同一时刻可能会存在多个入度为0的顶点,这些顶点在某一时刻的安排次序是任意的,这就可能会有多个拓扑序列产生,这是本文提出全拓扑排序算法的理论基础。
上一篇:混合云环境下基于失效感知的调度策略
下一篇:基于FitNium的Web关键字驱动的测试

vc++几种排序算法演示软件实现

VC++在线学习平台的设计

VC++BlackList的主机防火墙设计+源代码

VC++五子棋游戏的设计

VC++基于GPU高光谱图像目标检测方法

基于VC++五子连珠游戏的设计

基于VC++俄罗斯方块游戏的设计

AT89C52单片机的超声波测距...

公寓空调设计任务书

10万元能开儿童乐园吗,我...

C#学校科研管理系统的设计

志愿者活动的调查问卷表

承德市事业单位档案管理...

神经外科重症监护病房患...

医院财务风险因素分析及管理措施【2367字】

中国学术生态细节考察《...

国内外图像分割技术研究现状