数据结构与算法（十五）——图的拓扑排序和关键路径
一、拓扑排序
1，拓扑排序是什么？
（1）AOV网
AOV，Activity On Vertex Network，即顶点活动网。一个工程常常会被分为多个小的子工程，这些子工程被称为活动，在有向图中，若以顶点表示活动，有向边（也可以称为弧）表示活动之间的先后关系，这样的图简称为AOV网。
在工程的实施过程中，有些活动的开始是以它所有前序活动的结束为先决条件的，必须在其他有关活动完成之后才能开始；有些活动没有先决条件，可以安排在任意时间开始。AOV网就是一种可以形象地反映出整个工程中各个活动之间的先后关系的有向图。
如上图所示，有C1、C2、C3、C4、C5五个活动。
C1、C2的执行是没有先决条件的；C3必须要在C1、C2这两个活动都执行完毕之后才能够执行；C4必须要在C3执行完毕之后才可以执行；C5必须要在C4执行完毕之后才可以执行。
最终，我们将这些活动的执行顺序输出为一个线性的排序：C1->C2->C3->C4->C5，或者 C2->C1->C3->C4->C5。这种将AOV网中的活动进行排序就是拓扑排序，可以看到，拓扑排序是可能会有多种答案的，并不是只有唯一的答案。
（2）拓扑序列
在顶点活动网（AOV，Acticity On Vertex Network）中，若不存在回路，则所有活动可排列成一个线性序列，使得每一个活动的所有前驱活动都排列在该活动的前面，我们把此序列叫做拓扑序列。
假设G=(V, E)是一个具有n个顶点的有向图，V中的顶点序列V1、V2、V3……Vn满足若从顶点Vi到Vj有一条路径，则在顶点序列中Vi必在Vj的前面，则我们称这样的顶点序列为一个拓扑序列。
（3）拓扑排序
所谓的拓扑排序，实际上就是就是对一个有向图构造拓扑序列的过程。
需要注意的是，并非所有的有向图都可以成功构造出拓扑序列，因此在拓扑排序过程中，最终生成的顶点序列会有两种情况：
① 如果此网中的全部顶点都被输出，那说明该网是不存在环（回路）的AOV网；
②如果此网中的顶点没有被全部输出，哪怕只少了一个，那么也说明这个网是存在回路（环）的。
所以在最后，我们是需要通过判断所有顶点是否都被输出来判断拓扑排序的结果是否正确的。因为并非所有的有向图都可以成功进行拓扑排序的，只有无环的有向图才可以成功进行拓扑排序的。
2，拓扑排序的算法解析
（1）数据结构设计
AOV网图的存储采用邻接表的形式进行存储。关于邻接表存储，我在《数据结构与算法（十二）——图结构初探》中做过详细介绍，这里不再赘述。但是顶点活动网的线性表存储与一般的网图的线性表存储的结构的不同点在于，在顶点活动网的线性表结构设计中，关于顶点结构，除了有顶点值、边表指针这两个要素之外，还需要有一个“入度”的要素，如下图所示：
这里的in就是入度。
在顶点活动网（AOV，Activity On Vertex Network）中，某个顶点的入度指的就是指向该顶点的弧的条数。
如下图所示的AOV中，入度为0的顶点为V0、V1、V3：
顶点活动网（AOV，Activity On Vertex Network）的结构代码如下：
#include <stdio.h>
#include "stdlib.h"
#include <stdbool.h>
#pragma mark - AOV的结构
// AOV边表节点结构
typedef struct EdgeNode {
int vertexIndex; // 顶点下标
int weight; // 权重
struct EdgeNode *next; // 指针域，指向下一个
} EdgeNode;
// AOV顶点结构
typedef struct Vertex {
int in; // 入度
int data; // 顶点值
struct EdgeNode *firstEdge; // 指向边表链
} Vertex;
// AOV网图结构
typedef struct Graph {
struct Vertex *vertexes; // 邻接表
int countOfVertexes; // 顶点数
int countOfEdges; // 边数
} Graph;
// 创建一个图
void createGraph(Graph *graph) {
// 初始化顶点数、边数
printf("请输入顶点数：\n");
scanf("%d", &graph->countOfVertexes);
printf("请输入边数：\n");
scanf("%d", &graph->countOfEdges);
// 初始化顶点表
/*
1
2
3
4
5
6
7
8
9
10
11
12
13
14
*/
graph->vertexes = malloc(sizeof(Vertex) * graph->countOfVertexes);
printf("请依次输入%d个顶点值：\n", graph->countOfVertexes);
for (int i = 0; i < graph->countOfVertexes; i++) {
scanf("%d", &graph->vertexes[i].data);
graph->vertexes[i].in = 0;
graph->vertexes[i].firstEdge = NULL;
}
// 初始化边表信息
/*
0,4,1
0,5,1
0,11,1
1,2,1
1,4,1
1,8,1
2,5,1
2,6,1
2,9,1
3,2,1
3,13,1
4,7,1
5,8,1
5,12,1
6,5,1
8,7,1
9,10,1
9,11,1
10,13,1
12,9,1
*/
printf("请依次输入%d条边的信息，格式如下:\n弧尾，弧头，权重值\n", graph->countOfEdges);
int start, end;
for (int i = 0; i < graph->countOfEdges; i++) {
EdgeNode *edgeNode = malloc(sizeof(EdgeNode));
scanf("%d,%d,%d", &start, &end, &edgeNode->weight);
edgeNode->vertexIndex = end;
// 将新的边表节点前插到边表链的首元结点的位置
edgeNode->next = graph->vertexes[start].firstEdge;
graph->vertexes[start].firstEdge = edgeNode;
// 弧头顶点的入度加1
graph->vertexes[end].in++;
}
}（2）算法思路
基本思路如下：
从AOV中选择一个入度为0的顶点，做打印处理，然后将该顶点从图中删掉，并且删除以该顶点为弧尾的弧。重复上述动作，直到输出图中全部顶点或者顶点活动网（AOV）中不存在入度为0的顶点为止。
代码思路如下：
1，新建一个顺序栈stack，用于存储所有的入度为零的顶点；新建count变量用于记录处理已经处理过的顶点数量
2，遍历当前图中所有的入度为0的顶点，然后入栈
3，循环遍历栈中所有元素，步骤如下：
（1）处理打印当前栈顶元素并出栈
（2）count变量加1
（3）遍历以当前顶点为弧尾的所有的边，并移除这些边，具体操作如下：
①找到弧头顶点，并令其入度减一
②如果入度减1之后的弧头顶点的入度为0了，则入栈
代码如下：
#pragma mark - 拓扑排序
/*
1，新建一个顺序栈stack，用于存储所有的入度为零的顶点；新建count变量用于记录处理已经处理过的顶点数量
2，遍历当前图中所有的入度为0的顶点，然后入栈
3，循环遍历栈中所有元素，步骤如下：
（1）处理打印当前栈顶元素并出栈
（2）count变量加1
（3）遍历以当前顶点为弧尾的所有的边，并移除这些边，具体操作如下：
①找到弧头顶点，并令其入度减一
②如果入度减1之后的弧头顶点的入度为0了，则入栈
*/
void topoSort(Graph graph) {
/*
1，新建一个顺序栈stack，栈中存储所有的未处理过的入度为0的顶点；
新建一个变量count，用于记录已经处理过的入度为0的顶点的个数
*/
int stack[graph.countOfVertexes];
int stackTop = -1; // 栈顶指针
int count = 0;
/*
2，将所有的入度为0的顶点入栈
*/
for (int i = 0; i < graph.countOfVertexes; i++) {
if (graph.vertexes[i].in == 0) {
stack[++stackTop] = i;
}
}
/*
3，遍历栈中顶点元素：
（1）处理打印当前的栈顶元素，并出栈
（2）count变量（已经处理过的入度为0的顶点个数）加1
（3）遍历以当前顶点为弧尾的所有的边:
① 获取到弧头，并将弧头入度减1
② 将减1后的入度为0的弧头顶点入栈
*/
while (stackTop >= 0) {
// 处理并出栈
Vertex currentVertex = graph.vertexes[stack[stackTop--]];
printf("%d ", currentVertex.data);
// 数量+1
count++;
// 处理各个弧头顶点
for (struct EdgeNode *edgeNode = currentVertex.firstEdge; edgeNode; edgeNode = edgeNode->next) {
// 弧头顶点入度减1，当入度为0的时候入栈
if (--graph.vertexes[edgeNode->vertexIndex].in == 0) {
stack[++stackTop] = edgeNode->vertexIndex;
}
}
}
// 4，判断拓扑排序是否成功
if (count == graph.countOfVertexes) {
printf("\n拓扑排序成功!\n");
} else {
printf("\n拓扑排序失败!\n");
}
}
int main(int argc, const char * argv[]) {
Graph graph;
createGraph(&graph);
topoSort(graph);
return 0;
}二、关键路径
1，什么是AOE网
前面我们讲了AOV（顶点活动网，Activity On Vertexes Network），针对AOV还讲了拓扑排序，接下来我们就来讲讲AOE。
AOE，边活动网，Activity On Edges Network。
AOE是建立在AOV的基础上的，其实这很容易想明白，通过AOV的拓扑排序我们最终会获取到一条完整路径，而通过AOE我们是需要求得关键路径的，连一条完整的路径都求不出来的话是不可能求得关键路径的，所以AOE是建立在AOV的基础上的。二者的不同点在于：
①AOE是边活动网，它是以边表示活动，而顶点表示的是事件；AOV是顶点活动网，它是以顶点表示活动。
②AOE的边是有权值的，该权值表示的就是对应活动执行所需的时间
如上图所示，就是一个AOE网。在AOE网中，弧表示活动，弧上的权重表示完成该活动所需要的时间，例如a1=6表示完成a1活动所需的时间是6天；AOE网中的每一个顶点表示的是，在它之前的活动已经完成，可以开始后边的活动，例如顶点V5表示的是a4、a5俩活动均已完成，a7、a8活动可以开始。
使用AOE网可以解决这样的问题：如果将AOE网看成是整个项目，那么完成整个项目至少需要多长时间？
解决这个问题的关键就在于：在AOE网中找出一条从起始点到结束点长度最长的路径，这样就能够所有的活动在结束点抵达之前都能够完成。
在AOE网中，起始点指的是入度为0的点，称为“源点”；结束点是出度为0的点，称为“汇点”。一般而言，在AOE网中，只有一个源点和一个汇点，从源点到汇点长度最长的那一条路径，我们称之为“关键路径”。
为了求出给定AOE网的关键路径，我们需要知道如下四个统计数据：
针对AOE的顶点有两个时间：事件最早发生时间etv[j]（earlist time of vertex），事件最晚发生事件ltv[j]（latest time of vertex）；
针对AOE的弧有两个时间：活动最早开始时间ete[i]（earlist time of edge），活动最晚开始时间lte[i]（latest time of edge）。
（1）事件最早发生时间etv
对于顶点 j 来说，从源点到该顶点的最长路径代表着该顶点事件的最早发生时间，使用etv[j]来表示。
例如，上图中从V1到V5有两条路径。V1作为源点事件发生之后，a1和a2这俩活动同时开始执行，但是由于a1、a2这两条活动的执行时间是不一样的，因此最终V1->V3->V5这条路径会率先完成。但是这并不意味着此时事件V5就可以发生（即V5后面的活动可以执行）了，V5事件还需要等待V1->V2->V5这条路径也完成之后才能发生。所以对于V5来说，etv[5] = 6 + 1 = 7。
（2）事件最晚发生时间ltv
ltv[j] 表示的是，在不推迟整个工期的前提下，事件 Vj 所允许的最晚发生时间。
例如，在上图中，在得知整个工期是18天的前提下，事件V7最晚要在第16天的时候发生，因为活动a10的执行最少需要2天的时间才能完成，如果事件V7再推迟的话，整个工期就势必会被拖延，。因此，对于V7来说，其最晚发生时间ltv[7] = 16。
（3）活动最早开始时间ete
ete[i]表示的是活动ai开始执行的最早时间，如果ai是由弧<Vm, Vn>表示的，那么活动 ai 的最早开始时间其实就等于事件Vm的最早发生时间，即ete[i] = etv[m]。
其实这很好理解，例如上图中的
（4）活动最晚开始时间lte
lte[i]表示的是活动 ai 的最晚开始时间，如果ai是由弧<Vm, Vn>表示的，那么活动 ai 的最晚开始时间的设定要保证顶点事件 Vn 的最晚发生时间不拖后。因此，lte[i] = ltv[n] - weight<ai>。
在获取到上面的四种统计数据后，就可以直接求得AOE网中关键路径上的所有的关键活动了，方法是：对于所有的弧来说，如果它的最早开始时间等于最晚开始时间，那么称这条弧所代表的活动为关键活动，由关键活动所构成的路径称为关键路径。
2，算法
整体的算法思路如下：
1，通过拓扑排序获取到顶点事件的最早发生时间etv
2，获取顶点事件的最晚发生时间ltv
（1）创建ltvs数组，并将所有元素初始化为etvs数组中最大的那一个元素
（2）遍历拓扑排序之后的顶点数组topoStack，该数组是一个栈结构，处于栈顶的顶点元素是拓扑排序的最后一个顶点，在AOE网中即汇点。在每一次遍历中都要处理以当前顶点为弧尾的弧，具体操作为：
【弧头顶点的ltv - 弧的权重值】如果更小的话，则将其更新为弧尾顶点事件的最迟发生时间。
3，两层遍历（先遍历顶点，再遍历顶点的边），求得每一条边活动的最早开始时间ete和最晚开始时间lte，如果二者相等则说明该边在关键路径上。
（1）AOE网的创建以及拓扑排序
由于AOE是建立在AOV的基础之上的，所以求关键路径肯定需要先进行拓扑排序。拓扑排序的目的是求得两个东西：拓扑排序之后的顶点序列topoStack，各个顶点事件的最早发生时间etvs。
AOE网的拓扑排序实际上是从源点按某种次序一直遍历到汇点，因此拓扑排序之后的顶点序列topoStack的栈顶元素其实就是汇点顶点。
代码如下：
//
// main.c
// 关键路径
//
// Created by 拉维 on 2022/5/6.
//
#include <stdio.h>
#include "stdlib.h"
#pragma mark - 创建一个图
// 边表节点
typedef struct EdgeNode {
int vertexIndex; // 弧头顶点下标
int weight; // 弧的权重
struct EdgeNode *next; // 指针域
} EdgeNode;
// 顶点结构
typedef struct Vertex {
int in; // 入度
int data; // 顶点值
struct EdgeNode *firstEdgeNode; // 边表
} Vertex;
// 图结构
typedef struct Graph {
Vertex *vertexes; // 顶点表
int countOfVertexes; // 顶点数
int countOfEdges; // 边数
} Graph;
// 创建一个图
void createGraph(Graph *graph) {
// 初始化顶点数和边数
printf("请输入顶点数:\n");
scanf("%d", &graph->countOfVertexes);
printf("请输入边数:\n");
scanf("%d", &graph->countOfEdges);
// 初始化顶点表
printf("请依次输入%d个顶点值\n", graph->countOfVertexes);
graph->vertexes = malloc(sizeof(Vertex) * graph->countOfVertexes);
for (int i = 0; i < graph->countOfVertexes; i++) {
scanf("%d", &graph->vertexes[i].data);
graph->vertexes[i].in = 0;
graph->vertexes[i].firstEdgeNode = NULL;
}
// 初始化边表信息
printf("请依次输入%d条边表信息，格式如下：\n弧尾下标,弧头下标,权重值\n", graph->countOfEdges);
for (int i = 0; i < graph->countOfEdges; i++) {
struct EdgeNode *node = malloc(sizeof(EdgeNode));
int head, tail;
scanf("%d,%d,%d", &tail, &head, &node->weight);
node->vertexIndex = head;
node->next = graph->vertexes[tail].firstEdgeNode;
graph->vertexes[tail].firstEdgeNode = node;
graph->vertexes[head].in++;
}
}
#pragma mark - 拓扑排序
void topoSort(Graph graph, int *etvs, int *topoStack, int *topoStackTop) {
// 新建栈等变量
int zeroInStack[graph.countOfVertexes]; // 承载入度为0的栈
int zeroInStackTop = -1; // 栈顶指针
int count = 0; // 记录已经处理过的顶点个数
for (int i = 0; i < graph.countOfVertexes; i++) {
etvs[i] = 0; // 各个顶点事件的最早发生时间均初始化为0
}
// 遍历所有顶点，将入度为0的顶点全部入栈
for (int i = 0; i < graph.countOfVertexes; i++) {
if (graph.vertexes[i].in == 0) {
zeroInStack[++zeroInStackTop] = i;
}
}
// 依次遍历栈中顶点元素
while (zeroInStackTop >= 0) {
// 处理当前的栈顶顶点，并出栈
int currentVertexIndex = zeroInStack[zeroInStackTop--]; // 获取当前栈顶顶点下标并出栈
Vertex currentVertex = graph.vertexes[currentVertexIndex]; // 获取当前栈顶顶点
printf("%d ", currentVertex.data); // 打印栈顶顶点的值
topoStack[++(*topoStackTop)] = currentVertexIndex; // 将当前栈顶顶点的下标存到拓扑栈当中
// count用于最终判断拓扑排序是否成功
count++;
// 处理以当前顶点为弧尾的各条边
for (struct EdgeNode *edgeNode = currentVertex.firstEdgeNode; edgeNode; edgeNode = edgeNode->next) {
// 弧头入度减1，如果减1后入度为0则入栈
if (--graph.vertexes[edgeNode->vertexIndex].in == 0) {
zeroInStack[++zeroInStackTop] = edgeNode->vertexIndex;
}
// 更新弧头事件的最早发生时间etv
if (etvs[currentVertexIndex] + edgeNode->weight > etvs[edgeNode->vertexIndex]) {
etvs[edgeNode->vertexIndex] = etvs[currentVertexIndex] + edgeNode->weight;
}
}
}
// 检查拓扑排序的正确性
if (count == graph.countOfVertexes) {
printf("成功进行拓扑排序");
} else {
printf("拓扑排序有误");
}
printf("\n");
}（2）关键路径
前面通过拓扑排序已经求得了各个顶点事件的最早发生时间etvs，接下来的目的就是求得各个顶点事件的最晚发生时间ltvs。
etvs和ltvs这两个都已经求出来之后，就可以遍历AOE网中的每一条边，当前边活动的最早开始时间ete是弧尾顶点事件的最早发生时间；当前边活动的最晚开始时间lte是，弧头顶点事件的最晚发生时间➖当前边的权重值。
求得ete和lte之后，判断二者是否相等，如果相等则说明当前边在关键路径上。
那么各个顶点事件的最晚发生时间ltvs应该怎么去求呢？
前面我们说到，拓扑排序之后获取到的顶点数组topoStack是一个栈结构，处于栈顶的顶点元素是拓扑排序的最后一个顶点，在AOE网中即汇点。因此我们就遍历topoStack栈，然后获取到当前处于栈顶的顶点元素，遍历以此顶点为弧尾的每一条边，如果弧头顶点的最迟发生时间➖当前边的权重＜当前栈顶顶点的最迟发生时间，那么就将【当前栈顶顶点的最迟发生时间】更新为【弧头顶点的最迟发生时间➖当前边的权重】。
这样的话一波循环下来就可以求得最终的各个顶点的最迟发生时间ltvs了。
代码如下：
#pragma mark - 关键路径
/*
1，通过拓扑排序获取到顶点事件的最早发生时间etv
2，获取顶点事件的最晚发生时间ltv
（1）创建ltvs数组，并将所有元素初始化为etvs数组中最大的那一个元素
（2）遍历拓扑排序之后的顶点数组topoStack，该数组是一个栈结构，处于栈顶的顶点元素是拓扑排序的最后一个顶点，在AOE网中即汇点。在每一次遍历中都要处理以当前顶点为弧尾的弧，具体操作为：
【弧头顶点的ltv - 弧的权重值】如果更小的话，则将其更新为弧尾顶点事件的最迟发生时间。
3，两层遍历（先遍历顶点，再遍历顶点的边），求得每一条边活动的最早开始时间ete和最晚开始时间lte，如果二者相等则说明该边在关键路径上。
*/
void creticalPath(Graph graph) {
// 1，进行拓扑排序，获取到拓扑之后的顶点序列以及各个顶点事件的最早发生时间
int etvs[graph.countOfVertexes]; // 顶点事件的最早发生时间
int topoStack[graph.countOfVertexes]; // 拓扑排序之后的顶点序列
int topoStackTop = -1; // 栈顶指针
topoSort(graph, etvs, topoStack, &topoStackTop);
// 2，获取顶点事件的最迟发生时间
// 2.1 新建ltvs数组并初始化
int ltvs[graph.countOfVertexes];
for (int i = 0; i < graph.countOfVertexes; i++) {
// 将各个顶点的最晚发生时间均设置为项目的deadline
ltvs[i] = etvs[graph.countOfVertexes - 1];
}
// 2.2 遍历拓扑排序之后的顶点数组
while (topoStackTop >= 0) {
// 2.2.1 出栈
int currentVertexIndex = topoStack[topoStackTop--]; // 当前栈顶顶点的下标
// 2.2.2 遍历以当前栈顶顶点为弧尾的各条弧
struct EdgeNode *edgeNode;
for (edgeNode = graph.vertexes[currentVertexIndex].firstEdgeNode; edgeNode; edgeNode = edgeNode->next) {
int headVertexIndex = edgeNode->vertexIndex; // 弧头顶点下标
// 将弧尾顶点事件的最晚发生时间更新为最小的
if (ltvs[headVertexIndex] - edgeNode->weight < ltvs[currentVertexIndex]) {
ltvs[currentVertexIndex] = ltvs[headVertexIndex] - edgeNode->weight;
}
}
}
// 2.3 双层遍历，遍历到每一条边
struct EdgeNode *edgeNode;
int headVertexIndex, tailVertexIndex; // 弧头弧尾下标
int ete, lte; // 边活动的最早、最晚开始时间
for (int i = 0; i < graph.countOfVertexes; i++) {
for (edgeNode = graph.vertexes[i].firstEdgeNode; edgeNode; edgeNode = edgeNode->next) {
tailVertexIndex = i; // 弧尾顶点下标
headVertexIndex = edgeNode->vertexIndex; // 弧头顶点下标
ete = etvs[tailVertexIndex]; // 边活动的最早开始时间
lte = ltvs[headVertexIndex] - edgeNode->weight; // 边活动的最晚开始时间
if (ete == lte) { // 当边活动的最早开始时间与最晚开始时间一致的时候，说明是关键路径
printf("关键路径<%d, %d>=%d\n", graph.vertexes[tailVertexIndex].data, graph.vertexes[headVertexIndex].data, edgeNode->weight);
}
}
}
}
int main(int argc, const char * argv[]) {
Graph graph;
createGraph(&graph);
creticalPath(graph);
return 0;
}
以上。
腾讯云开发者
