拓扑排序

目录

一、系统开发的背景 .......................................................................... 1

（一）

（二）

（三）

（四） 问题描述 ........................................................................................................................................ 1 任务要求 ........................................................................................................................................ 1 测试数据 ........................................................................................................................................ 2 系统模块结构设计 ........................................................................................................................ 2

三、系统的设计与实现 ...................................................................... 3

（一）

（二）

（三） 系统流程图： ................................................................................................................................ 3 主函数模块 .................................................................................................................................... 4 图存储结构的建立 ........................................................................................................................ 4

四、系统测试 ....................................................................................... 8

（一）

（二）

（三） 测试界面选择的实现 .................................................................................................................... 8 测试拓扑排序的实现 .................................................................................................................... 8 测试关键活动的实现 .................................................................................................................... 8

五、总结 ............................................................................................... 9

六、附件（代码、部分图表） ........................................................ 10

拓扑排序

一、系统开发的背景

为了在科技不断进步的今天能够紧跟着时代的步伐，人们开始不断地追求方便和快捷的生活方式，在这个新鲜的时代，越来越多的新鲜事物层出不穷，为人们提供着各种方便和便利，为了更好地适应和接受这个时刻进步着的社会，我们要努力赶上。在实际工作中，经常要使用一个有向图来表示工程的施工流程或者产品生产的流程图。也就是说，一个大的工程经常被划分为若干个较小的子工程，这些子工程称为“活动”（Activity）。当这些子工程全部完成时，整个工程也就完成了。并且更要关心整个工程完成的最短时间，这就是有向权图的另一个重要应用——工程进度的关键路径问题。用图的邻接表（出边表）表示方法，实现拓扑排序和关键路径的求解过程。

二、系统分析与设计

（一） 问题描述

拓扑排序可判断AOV网络中是否存在回路，使得所有活动可排成一个线性序列，使用每个活动的所有前驱活动都排在该活动的前面。

关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。

（二） 任务要求

构建AOV网络，并输出其拓扑序列结果，输出该图的关键路径和关键活动，存储结构自行选择。

1

（三） 测试数据

自行设定(结点数不少于10个)。

（四） 系统模块结构设计

分析：此问题实现需采用拓扑排序和关键路径实现AOV网的拓扑排序和AOE网的关键路径求法，而在求关键路径过程中又用到了拓扑排序来判断图中是否存在回路。为了保持图的初始化一致性，虽然在拓扑排序算法中不需要求边的权值，但关键路径需要。所以在输入图的时候都规定了一种格式：（v1,v2,w1），表示边（v1,v2）上的权值为w1。

通过对系统功能的分析，拓扑排序的实现功能如图1所示。

图1拓扑排序的实现功能图

通过上图的功能分析，把整个系统划分为4个模块：

1、完成对图的建立，该模块主要实现：完成数据的存储，并将数据引

2

入AOV网中；

2、AOE网的拓扑排序，该模块主要实现：使得所有活动可排成一个线性序列，使用每个活动的所有前驱活动都排在该活动的前面进行排序；

3、 AOE网的关键路径，该模块主要实现：找出众多活动中的某条具体关键路径；

4、 实现对结果的正确输出，该模块主要实现：对结果的正确输 出与检测；

三、系统的设计与实现

（一） 系统流程图：

3