VC++有向无环图所有拓扑序列的生成(2)
3.1 全拓扑排序算法的概述 15
3.2 全拓扑排序算法的具体实现 15
3.2.1全拓扑排序算法流程图 15
3.2.2 实例应用 17
3.2.3 全拓扑排序算法的核心代码 18
3.3 算法的复杂度 19
3.4 全拓扑排序算法的实际应用 20
3.5.1 AOV网图外部不可见点的问题 20
3.5.2拓扑序列决策问题 21
3.5.3 并行子工程的安排 22
第四章 基于MFC的并行拓扑算法的实现 23
4.1 MFC编程的概念 24
4.2 系统功能的划分 24
4.3 输入的设计 24
4.3.1 顶点和边的基本信息输入 24
4.3.2 决策信息的输入 25
4.4 查看求解过程 25
4.4.1 所有拓扑序列的输出 25
4.4.2 决策选择后的拓扑序列 27
第五章 程序测试及性能分析 33
5.1 程序测试 33
5.2 算法性能分析 34
结束语 35
致谢 36
参考文献 37
第一章 绪 论
1.1 引言
在数据结构这门学科中，拓扑排序算法思想的提出有着极其重要的意义。该思想在教学计划安排、工程施工管理、生产流程控制等领域发挥了很重要的作用。在实际工程中，一个完整的工程可以由若干个子工程（也称为活动）组成，这些子工程在安排的先后顺序上存在一定的制约关系，有的子工程必须在其他子工程完成之后才可以开始，而子工程之间的先后制约关系可能是比较复杂的。为了求得一个合理的子工程安排序列，必然要寻求一种算法进行求解。按这一顺序来安排各子工程可以保证整个工程的顺序进行，不至于出现后续子工程先于应该在它之前完成的子工程前面安排。在数据结构学科中，对于这一类问题，用图中的拓扑排序算法进行求解。
有向图的各顶点代表子工程（也称为活动），用有向边表示任务之间的优先关系，该边是从先前活动指向后续活动，这种有向图称为AOV网(Activity On Vertex Network)，要使AOV 网中的各个顶点排成一个线性序列，并且能够文持各个顶点之间原有的先后次序，这样的一个排序过程就是拓扑排序，所得到的线性序列称为拓扑序列。
求得了拓扑序列，就可以按序列中各子工程的先后顺序串行地安排各项活动，并且能够文持原有活动的先后次序关系。AOV网的拓扑序列不一定唯一，这就意着某些活动可以同时安排，从而缩短整个工程的时间。
下面的例子简单说明拓扑排序算法的应用。一个工程中有6个子工程，它们之间的先后次序制约关系如表1.1所示。
表1.1 各子工程的先后次序表
子工程号 紧前子工程
0 无
1 无
2 0，1
3 1
4 2
5 2，3
根据表1.1，得到对应的AOV网如图1.1所示。
图1.1 AOV网G1
根据拓扑排序列算法思想，可以求得表1.2所示的12个拓扑序列，按照其中任意一种序列的顺序安排活动，都能保证整个工程的顺利完成。
表1.2 12个拓扑序列
拓扑序列1 0，1，2，3，4，5
拓扑序列2 0，1，2，3，5，4
拓扑序列3 0，1，2，4，3，5
拓扑序列4 0，1，3，2，4，5