有向图的拓扑排序和逆拓扑排序实验指导 1基本内容 对于给定的有向工程施工图，找出该工程图的关键活动。

拓扑排序是指将有向无环图（DAG）的所有顶点排成一个线性序列，使得图中任意一条有向边的终点（被指向的顶点）在序列中都排在起点（指向它的顶点）的前面。拓扑排序常用于确定计算任务的先后顺序，比如在编译程序时确定编译顺序、在工程项目中确定任务的执行顺序等。

基本步骤如下：

1. 对于给定的有向图，从图中选择一个入度为0的顶点，并输出该顶点；
2. 从图中删除该顶点以及以该顶点为起点的所有有向边；
3. 重复1和2步，直到图中所有顶点都被输出。

关键活动是指在一个项目网络中，必须准确地完成某项任务，才能使整个项目按期完成。关键活动的特点是它们的总工期等于它们的最短工期，也就是说，如果其中任何一个关键活动被延误了，整个项目的工期都会受到影响。

找出给定有向图的关键活动的基本步骤如下：

1. 对有向图进行拓扑排序，得到一个顶点序列；
2. 对于每个顶点，计算其最早开始时间（EST）和最晚开始时间（LST）；
3. 对于每条边，计算其最早开始时间（EFT）和最晚开始时间（LFT）；
4. 对于每个关键活动，其EST和LST相等。

其中，最早开始时间（EST）表示在没有任何限制条件下，一个活动可以开始的最早时间；最晚开始时间（LST）表示最迟必须开始该活动的时间，超过这个时间，整个项目都将受到延误；最早完成时间（EFT）表示在没有任何限制条件下，一个活动可以完成的最早时间；最晚完成时间（LFT）表示最迟必须完成该活动的时间，超过这个时间，整个项目都将受到延误。

在实验中，可以先用邻接表或邻接矩阵表示有向图，然后进行拓扑排序和关键活动的计算。可以使用编程语言实现算法，也可以使用图形化工具实现。