文章目录
一、前言
理解关键路径需要掌握拓扑排序和邻接表的相关知识，由于此部分笔者在之前的文章中已经介绍过，此处不再过多赘述，对此部分知识还不熟练的读者，欢迎移步此文章，共同学习！：
数据结构C++——拓扑排序
数据结构C++——图的邻接矩阵和邻接表
二、关键路径的概念
（1）AOE-网:与AOV-网相对应的是AOE-网 , 即以边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。
（2）源点和汇点：由于整个工程中只有一个开始点和一个完成点，故在正常的情况（无环）下数据结构关键路径 数据结构C++——关键路径，网中只有一个入度为零的点，称作源点，也只有一个出度为零的点，称作汇点。
（3）关键路径和关键活动：要估算整项工程完成的最短时间， 就是要找一条从源点到 汇点的带权路径长度最长的路径，称为关键路径。关键路径上的活动叫做关键活动，这些活动是影响工程进度的关键， 它们的提前或拖延将使整个工程提前或拖延。
三、关键路径的实现 ①关键路径的实现原理
关键路径算法的实现需要引入两个辅助数组ve[i]和vl[i]，分别用来记录事件vi的最早发生时间和记录事件vi的最迟发生时间。遍历整个topo数组，计算出其中存放的顶点（事件）最早发生时间，按逆拓扑序列求出每个事件的最迟发生时间。求出每个边（活动）的最早开始时间和最晚开始时间，边（活动）最早开始时间和最晚开始时间相等的边（活动）即为关键活动。由关键活动形成的由源点到汇点的每一条路径就是关键路径。
②关键路径的代码实现
关键路径的代码实现
关键路径算法思路：
1：给每个时间的最早发生时间置初值为0
2：取得拓扑序列中的顶点，并遍历该顶点的所有邻接点，更新邻接点（事件）发生的最早时间
3：取得逆拓扑序列中的顶点，遍历该顶点的所有邻接点，更新邻接点（事件）发生的最迟时间
4：遍历顶点表，输出最早发生时间和最迟发生时间相等的某边（活动）所依附的两个顶点输出
<p><pre>/---------关键路径算法---------/
Status CriticalPath(ALGraph& G) {
//G为邻接表存储的有向图，输出G的各项关键活动
if (!TopologicalSort(G, topo)) return ERROR;
//调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR
int n = G.vexnum;//n为顶点个数
for (int i = 0; i weight;
p = p->nextarc;//p指向k的下一个邻接顶点
}
}
for (int i = 0; i = 0; i--) {
int k = topo[i];//取得拓扑序列中的顶点序号k
ArcNode* p = new ArcNode;
p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点
while (p != NULL) {//根据k的邻接点，更新k的最迟发生时间
int j = p->adjvex;//j为邻接顶点的序号
if (vl[k] > vl[j] - p->weight)//更新顶点k的最迟发生时间vl[k]
vl[k] = vl[j] - p->weight;
p = p->nextarc;//p指向k的下一个邻接顶点
}
}
/*-----------判断每一个活动是否为关键活动--------------*/
for (int i = 0; i adjvex;//j为邻接顶点的序号
int e = ve[i];//计算活动的最早开始时间
int l = vl[j] - p->weight;//计算活动的最迟开始时间
if (e == l)
cout v1 >> v2 >> w;
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
ArcNode* p1 = new ArcNode;
p1->adjvex = j;
p1->weight = w;
p1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p1;
}}
void FindInDegree(ALGraph G, int indegree[]) {
for (int i = 0; i nextarc;//指针不断向后指
}
indegree[i] = cnt;//将计数结果保留在indegree数组中
}
}}
/----------拓扑排序算法---------------/
Status TopologicalSort(ALGraph G, int topo[]) {
//有向图G采用邻接表存储结构
//若G无回路，则生成G的一个拓扑排序topo[]并返回OK，否则ERROR
FindInDegree(G, indegree);//求出各结点的入度存入数组indegree中
SqStack S;
InitStack(S);//初始化栈
for (int i = 0; i adjvex;//vk为vi的邻接点
--indegree[k];//vi的每个邻接点的入度减一
if (indegree[k] == 0) Push(S, k);//若入度减为0，则入栈
p = p->nextarc;//p指向顶点vi下一个邻接结点
}
}
if (m nextarc;//p指向k的下一个邻接顶点
}
}
for (int i = 0; i = 0; i--) {
int k = topo[i];//取得拓扑序列中的顶点序号k
ArcNode* p = new ArcNode;
p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点
while (p != NULL) {//根据k的邻接点，更新k的最迟发生时间
int j = p->adjvex;//j为邻接顶点的序号
if (vl[k] > vl[j] - p->weight)//更新顶点k的最迟发生时间vl[k]
vl[k] = vl[j] - p->weight;
p = p->nextarc;//p指向k的下一个邻接顶点
}
}
/*-----------判断每一个活动是否为关键活动--------------*/
for (int i = 0; i adjvex;//j为邻接顶点的序号
int e = ve[i];//计算活动的最早开始时间
int l = vl[j] - p->weight;//计算活动的最迟开始时间
if (e == l)
cout