VC++有向无环图所有拓扑序列的生成
时间:2017-06-09 23:08 来源:毕业论文 作者:毕业论文 点击:次
| 摘要拓扑排序算法是在AOV网中求顶点的拓扑序列的一种方法，该算法在工程管理、系统统筹调度、生产流程控制及软件开发等领域得到了广泛应用。传统的基于栈结构的拓扑排序算法只能求得一种拓扑序列。而在实际工程安排中，若因为特殊情况无法按这一种指定的顺序安排子工程，将无法确知其他可能的选择，拓扑排序算法的实用价值降低。 本论文对AOV网提出了全拓扑排序算法（Overall Topological Sort Algorithm），该算法采用邻接表数据结构（实际操作中用vector来代替邻接表），按分层处理的方法求AOV网中顶点的所有拓扑序列。本论文在VC++下实现了全拓扑排序算法求得了所有拓扑序列，并且在若干子工程安排上有特殊需求时，根据算法的计算结果从多个拓扑序列中挑选出满足条件的特定拓扑序列，从而保证整个工程的顺利进行。论文还分析了并行安排子工程的可行性。总之，全拓扑排序算法提升了拓扑排序算法的实用价值。10005 关键词 拓扑排序算法； AOV网； 拓扑序列； 全拓扑排序算法；邻接表数据结构；实用价值 毕业设计说明书（论文）外文摘要 Title An algorithm to generate all topological sorting arrangements of the directed acyclic graph Abstract The Topological Sort Algorithm is an algorithm to work out topological lists of all vertexes in an AOV network. This algorithm is widely used in various fields such as engineering management, coordinative system scheduling, production process controlling and software developing.Based on stack, the traditional topological sort algorithm can work out only one topological list. But in practical projects’ arrangement, if there are some unexpected circles, the sub-engineering can not be arranged according to the certain unique topological list. Any other possible choice for arrangement is unknown, so the apply value of the Topological Sort Algorithm is debased. This thesis brings forward the Overall Topological Sort Algorithm called PTSA. This algorithm uses Adjacency List data structure, and it can work out all the topological lists in AOV net through a level-based method. This thesis gets all the feasible topological lists by using Overall Topological Sort Algorithm in the VC++ developing environment. Meanwhile, it picks out the certain topological sort from all the topological sorts worked out by Overall Topological Sort Algorithm when some sub- engineerings have special demand in engineering arrangement,so it ensures the whole engineering can go on wheels.This thesis also analyzes the feasibility of arranging sub-enginerrings in parallel way. In a word, the Overall Topological Sort Algorithm improves the apply value of Topological Sort Algorithm. Keywords Topological Sort Algorithm； AOV Network； Topological List； Overall Topological Sort Algorithm； Adjacency List Data Structure；Apply Value 目 录 第一章 绪 论 4 1.1 引言 4 1.2 课题研究的背景 5 1.3 论文的组织 6 第二章 拓扑排序算法研究的现状 7 2.1 拓扑排序算法的基本概念 7 2.1.1 定义和术语 7 2.1.2 拓扑排序的思想 8 2.2 基于栈结构的单拓扑序列求解方法 9 2.2.1 图的存储结构 10 2.2.2 基于栈得到单拓扑序列的原理 11 2.2.3 单拓扑算法的时间复杂度 13 2.3 栈的缺陷带来的启发 14 第三章 全拓扑排序算法的设计 15 (责任编辑：qin) |