VC++有向无环图所有拓扑序列的生成(3)
时间:2017-06-09 23:08 来源:毕业论文 作者:毕业论文 点击:次
拓扑序列5 0，1，3，2，5，4 拓扑序列6 1，0，2，3，4，5 拓扑序列7 1，0，2，3，5，4 拓扑序列8 1，0，2，4，3，5 拓扑序列9 1，0，3，2，4，5 拓扑序列10 1，0，3，2，5，4 拓扑序列11 1，3，0，2，4，5 拓扑序列12 1，3，0，2，5，4 1.2 课题研究的背景 从以上的例子可以看到，一个AOV网中可能存在多个拓扑序列，如何通过程序求得所有的拓扑序列？这是在数据结构学科中一直没能得到很好解决的问题。因为现有的求拓扑序列的算法是基于栈结构的，只能求出某一种拓扑序列，这样在实际工程安排时只有这一种次序的参考信息，按照这个序列去安排各个子工程，一定能够保证整个工程顺利完成。但在实际工程中，若出现某种意外，无法按这一指定的顺序安排工程，那么就不能确知其它可能的选择；另一方面，在人手和资源许可的情况下，也可以让多个子工程并行的进行，在仅有一个拓扑序列的情况下得不到并行信息。因此，以往的程序不能解决这两个实际工程进度安排中实际存在的问题，这就使得这种拓扑排序算法的实际应用价值大打折扣。 针对这些不足，已有一些关于求所有拓扑序列方面的研究，《一种有向图并行全拓扑排序算法设计与实现》一文中，讨论了AOV网的一种并行性全拓扑排序的算法及实现，解决了传统拓扑排序算法的单一性问题，说明了并行全拓扑排序有重要的使用价值。 《关于拓扑排序算法的讨论》一文中，对AOV网的不同存储结构的拓朴排序，在传统算法的基础上提出了新的改进算法，并对这些算法的时间、空间复杂性进行了分析和比较，同时讨论了不同算法的适用范围。 《一种新的基于邻接矩阵的拓扑排序算法》为了降低基于邻接矩阵的拓扑排序算法的复杂性，将单顶点算法框架扩展成集合算法框架，给出一些便于进行拓扑排序的有向无环图的性质。在此基础上，定义了适合进行弧删除操作和无前驱顶点判断的邻接矩阵运算，给出了有向弧邻接矩阵的存储方案，最终提出了一种时间和空间复杂度都比较低的拓扑排序算法。 《算法设计技术在拓扑排序的运用》一文中，探讨了用多种计算机算法设计技术实现拓扑排序的思想，并且结合实例，提出了回溯法、分支限界法、贪婪算法、动态规划、等方法的具体解决思路及其排序过程。 《广度优先编历方式下拓扑排序算法的实现》一文中，讨论了图的广度优先编历方式及AOV网中活动之间的优先关系，对于活动的安排进行了拓扑排序算法的分析，并给出了相应的伪代码。 本论文提出了全拓扑排序算法（Overall Topological Sort Algorithm），重点是运用一种合理的数据结构，以存储结构为突破口实现求所有的拓扑序列。论文提出了一种基于层次和邻接表的数据结构，基于分层次处理的思想一次求出AOV网中顶点所有可能的拓扑序列，从而为实际工程的串行安排提供多种可能的选择，并使得并行安排子工程成为可能，提升了拓扑排序算法的实用价值。 1.3 论文的组织 本论文接下来主要分四个章节对拓扑排序算法进行详细的阐述。 第二章首先介绍了图的存储结构，并着重介绍了本算法用到的图的存储结构。然后从拓扑排序的思想入手，阐述了以往基于栈结构得拓扑排序算法为什么只能得到一种拓扑序列。并结合实例，具体地描述了基于栈结构的拓扑排序算法求得单个拓扑序列的全过程。最后还给出了该算法的核心代码及其该算法的时间复杂度。 (责任编辑：qin) |