VC++有向无环图所有拓扑序列的生成(4)
时间:2017-06-09 23:08 来源:毕业论文 作者:毕业论文 点击:次
第三章在前面单拓扑的基础上，提出了全拓扑排序算法。该算法对数据结构进行改进，提出了基于层次和邻接表的数据结构，基于层次思想求得所有的拓扑序列。这一章介绍全拓扑排序算法的概念，并通过流程图介绍全拓扑排序算法如何求得所有的拓扑序列。最后给出了全拓扑排序算法的核心代码，并对代码做了些解释，给出了该算法的时间复杂度。 第四章介绍了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的顶点，这些顶点在某一时刻的安排次序是任意的，这就可能会有多个拓扑序列产生，这是本文提出全拓扑排序算法的理论基础。 (责任编辑：qin) |