数据结构求关键路径实习报告(6)

用带权有向图构造的AOE网表示一项工程计划,图的结点表示事件,弧表示活动,权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期……

二、课题分析与设计

1．课题需求分析

1.1问题描述：

（1）选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。

（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。

具体要解决的问题有如下四个：

1） 将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列；

2） 用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图；

3） 用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差；

4） 找出所有时差为零的活动所组成的路线，即为关键路径； 1.2 基本要求

（1）选取建图的一种算法建立图；

选取邻接表的算法来建立图，是一种顺序+ 链式存储结构。用顺序表

存放顶点，为每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边或以该顶点为尾的弧。

（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。参照该工程所化的AOE-网，求出从起点到终点的所有路径，然后通过拓扑排序和逆拓扑排序求出最早与最晚发生时间，找出长度最大的路径，从而求得关键路径。 2．存储结构设计

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构求关键路径实习报告(6)在线全文阅读。