上次我们介绍了图的拓扑排序算法的实现，这次介绍基于邻接表的关键路径算法的实现。
还是老规矩：
程序在码云上可以下载。
地址：https://git.oschina.net/601345138/DataStructureCLanguage.git
本次关键路径程序共用到以下源文件，有一些已经在之前的文章介绍过。还是和以前一样，所有源文件需要放在同一目录下编译。
my_constants.h 各种状态码定义
LinkedList.cpp 不带头结点单链表各种基本操作的实现
ALGraph.h 图的邻接表存储结构表示定义
ALGraph.cpp 基于邻接表的图的基本操作实现
Stack.cpp 顺序栈的基本操作实现
CriticalPath.cpp 关键路径算法的实现
关键路径测试.cpp 主函数，调用算法完成关键路径程序的演示
为了操作实现方便，我使用了单链表程序来简化邻接表部分操作，但是这个单链表与《 数据结构编程笔记四：第二章 线性表 单链表的实现》一文介绍的单链表有所区别，本文用到的单链表不带头结点，很多操作与带头结点的单链表有区别。望读者注意。具体程序参见《数据结构编程笔记十九：第七章 图 图的邻接表存储表示及各基本操作的实现》；
邻接表在《数据结构编程笔记十九：第七章 图 图的邻接表存储表示及各基本操作的实现》一文有所介绍，my_constants.h、ALGraph.h 、ALGraph.cpp和LinkedList.cpp四个源文件与此文中的同名源文件内容完全一致，没有修改。这里不再重复贴了（否则文章会很长，不能突出重点），但在码云上你可以下载到全部源文件，我会把它放在一个目录下。
关键路径操作用到了拓扑排序的算法，如果不清楚拓扑排序过程的读者请参考《数据结构编程笔记二十二：第七章 图 拓扑排序算法的实现》。本次程序用到拓扑排序程序中的一个求顶点入度的函数。
拓扑排序操作在实现过程中使用了栈。我引入了已经实现的顺序栈来辅助完成拓扑排序。
顺序栈在《 数据结构编程笔记八：第三章 栈和队列 顺序栈和进位制程序的实现》一文中已经有所介绍，除了修改栈的数据类型为int，源代码其余部分我都没有改变。需要的读者可以参考《数据结构编程笔记二十二：第七章 图 拓扑排序算法的实现》这篇文章。我不再贴出源码。
任何一项工程都有若干事件和活动，这些事件和活动连接起来就是整个工程的流程。假设你是一名项目工程师，你所要做的工作就是设法加快项目进度，节约时间（软件工程中项目经理这个角色就得操心项目进度规划的事），工期每拖一天就要多支付工人一天的报酬，而且软件工程中的项目的进度不可能计划的那么死（恰到好处，一点不留余地），总要留点余地（缓冲时间），因为万一如果项目在进行过程中因为某种意外原因拖延了项目进度，就有可能导致项目在截止日期之前完不成，一旦项目超期，甲方（项目实施方，也就是你这一方）是要付违约金的（做项目没人想要赔钱）。
工程中的有的活动有先后顺序的制约，某些活动必须等其他活动结束后方可开始（串行）而有些则可以和其他活动一同进行（并行）。这些事件和活动会组成一张图（有向网）。软件工程项目中，事件相当于里程碑（标志整个工程进入某个阶段的重要结点），也就是图中的顶点；活动相当于每一项具体的工作，也就是图中的边。
在工程进度安排中，绝对不允许出现环路。原因是显而易见的：出现环路意味着一旦进入环路将会无法跳出，项目也就无法正常结束。这是不允许的。如果有项目经理安排了这样的进度。。。（显然不可能有人会这么做）
关键路径就是用于解决工程安排的问题，它的主要目的是找出整个工程流程中的关键流程，然后工程师会尝试设法缩短关键流程的时间，这样就可以起到加快整个工程进度，节约时间的目的。
计算关键路径之前，我们首先要保证图中没有环，所以自然就想到了拓扑排序。使用拓扑排序作为执行关键路径算法的先决条件，一旦拓扑排序不成功，说明图中必有环，那就没必要继续计算关键路径了。
本次只贴关键路径的核心代码和主函数：
源文件：CriticalPath.cpp
//打印关键路径用到的几个函数
void printhead(ALGraph G);
void printi(ALGraph G);
void printvex(ALGraph G);
void printve(ALGraph G, int ve[]);
void printvl(ALGraph G, int vl[]);
void printCritical1(ALGraph G, int ve[], int vl[]);
/*
函数：FindInDegree
参数：ALGraph G 图G（邻接表存储结构）
int indegree[] 存储顶点入度的数组
返回值：无
作用：求顶点的入度
*/
void FindInDegree(ALGraph G, int indegree[]) {
//工作指针p
ArcNode *p;
//对存储入度的indegree数组赋初值0
for(int i = 0; i < MAX_VERTEX_NUM; i++) {
indegree[i] = 0;
}//for
//扫描每个顶点后面的弧链表
for(int i = 0; i < G.vexnum; i++) {
//p指向顶点i后面弧链表的首元结点
p = G.vertices[i].firstarc;
//顶点v的弧链表没有扫描完毕
while(p) { //while(p) <=> while(p != NULL)
//每找到一个弧结点，对应邻接点的入度+1
indegree[p->data.adjvex]++;
//p指向下一个弧结点
p = p->nextarc;
}//while
}//for
}//FindInDegree
//事件最早发生时间，全局变量
int ve[MAX_VERTEX_NUM];
/*
函数：TopologicalOrder
参数：ALGraph G 图的邻接表存储表示
Stack &T 拓扑序列顶点栈
返回值：状态码，OK表示操作成功,ERROR表示操作失败
作用：有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量)。
若G无回路，则用栈T返回G的一个拓扑序列,且函数值为OK,否则为ERROR
*/
Status TopologicalOrder(ALGraph G, Stack &T) {
//count是已入栈顶点数，初值为0
int i = 0, k = 0, count = 0;
//入度数组，存放各顶点当前入度数
int indegree[MAX_VERTEX_NUM];
//S为零入度顶点栈。
Stack S;
//指向弧结点的工作指针p
ArcNode *p;
//对各顶点求入度并存入数组indegree[]
FindInDegree(G, indegree);
//初始化零入度顶点栈S
InitStack(S);
printf("->求得的拓扑序列：");
//对所有顶点i
for(i = 0; i < G.vexnum; ++i) {
//若其入度为0,将i压入零入度顶点栈S
//if(!indegree[i]) <=> if(indegree[i] == 0)
if(!indegree[i]) {
Push(S, i);
}//if
}//for
//初始化拓扑序列顶点栈
InitStack(T);
//初始化ve[]=0(最小值，先假定每个事件都不受其他事件约束)
for(i = 0; i < G.vexnum; ++i) {
ve[i] = 0;
}//for
//当零入度顶点栈S不空
//while(!StackIsEmpty(S)) <=> while(StackIsEmpty(S) == FALSE)
while(!StackIsEmpty(S)) {
//从栈S将已拓扑排序的顶点j弹出
Pop(S, i);
//打印出栈的序号为i的顶点
printf("%d ", G.vertices[i].data);
//j号顶点入逆拓扑排序栈T(栈底元素为拓扑排序的第1个元素)
Push(T, i);
//对入栈T的顶点计数
++count;
//对i号顶点的每个邻接点
for(p = G.vertices[i].firstarc; p; p = p->nextarc) {
//邻接点序号为k
k = p->data.adjvex;
//k的入度减1之后变为0，是零入度顶点，则将k入栈S
if(--indegree[k] == 0) {
Push(S, k);
}//if
//顶点k事件的最早发生时间要受其直接前驱顶点i事件的
//最早发生时间和<i,k>的权值约束。由于i已拓扑有序，故ve[i]不再改变
//*(p->data.info)是<i,k>的权值
if(ve[i] + *(p->data.info) > ve[k]) {
ve[k] = ve[i] + *(p->data.info);
}//if
}//for
}//while
//拓扑排序结束后若有顶点不在拓扑序列中说明图G存在回路
if(count < G.vexnum) {
printf("此有向网有回路\n");
return ERROR;
}//if
else {
return OK;
}//else
}//TopologicalOrder
/*
函数：CriticalPath
参数：ALGraph G 图的邻接表存储表示
返回值：状态码，OK表示操作成功
作用：输出G的各项关键活动
*/
Status CriticalPath(ALGraph G) {
//事件最迟发生时间
int vl[MAX_VERTEX_NUM];
Stack T;
int i, j, k, ee, el, dut;
//工作指针p
ArcNode *p;
//产生有向环
if(!TopologicalOrder(G, T)) {
return ERROR;
}//if
printf("\n->通过拓扑排序，图中没有环！\n");
//j的初值
j = ve[0];
//计算最早发生时间ve[]
for(i = 1; i < G.vexnum; i++){
//j = Max(ve[]) 完成点的最早发生时间
if(ve[i] > j) {
j = ve[i];
}//if
}//for
//初始化顶点事件的最迟发生时间
for(i = 0; i < G.vexnum; i++) {
//初始化所有顶点事件的最迟发生时间为完成点的最早发生时间(最大值)
vl[i] = j;
}//for
//按拓扑逆序求各顶点的vl值
while(!StackIsEmpty(T)) {
//弹出栈T的元素,赋给j,p指向j的后继事件k
for(Pop(T, j), p = G.vertices[j].firstarc; p; p = p->nextarc) {
//事件k的最迟发生时间已确定(因为是逆拓扑排序)
k = p->data.adjvex;
//dut=<j,k>的权值
dut = *(p->data.info);
//事件j的最迟发生时间要受其直接后继事件k的最迟发生时间
//和<j,k>的权值约束。由于k已逆拓扑有序，故vl[k]不再改变
if(vl[k] - dut < vl[j]) {
vl[j] = vl[k] - dut;
}//if
}//for
}//for
//打印表头
printhead(G);
//打印i
printi(G);
//打印顶点值
printvex(G);
//打印ve
printve(G, ve);
//打印vl
printvl(G, vl);
//打印关键路径是否经过此顶点
printCritical1(G, ve, vl);
//求ee，el和关键活动
printf("\n+------+------+------+------+------+----------+\n");
printf("| 活动（边） |\n");
printf("+------+------+------+------+------+----------+\n");
printf("| 弧尾 | 弧头 | 权值 | ee | el | 关键活动 |\n");
printf("+------+------+------+------+------+----------+\n");
for(j = 0; j < G.vexnum; ++j) {
//p指向j的邻接点k
for(p = G.vertices[j].firstarc; p; p = p->nextarc) {
k = p->data.adjvex;
//dut=<j,k>的权值
dut = *(p->data.info);
//ee=活动<j,k>的最早开始时间(在j点)
ee = ve[j];
//el=活动<j,k>的最迟开始时间(在j点)
el = vl[k] - dut;
//打印ee和el的值
printf("| %4d | %4d | %3d | %3d | %3d |%s|\n",
G.vertices[j].data, G.vertices[k].data, dut, ee, el,
ee == el ? " √ " : " ");
printf("+------+------+------+------+------+----------+\n");
}//for
}//for
//操作成功
return OK;
}//CriticalPath
/*
函数：printhead
参数：ALGraph G 图G（邻接表表示）
返回值：无
作用：打印表头
*/
void printhead(ALGraph G) {
//第一行
printf("\n+-----------");
for(int i = 0; i < G.vexnum - 1; i++) {
printf("------");
}//for
printf("-----+\n|");
//第二行：字符数：12
//中间位置：[(10 + 1) + G.vexnum * (5 + 1) - 1 - 12] / 2
// <=> (6 * G.vexnum - 2) / 2
int count = 6 * G.vexnum - 2;
for(int i = 0; i < count / 2 ; i++) {
printf(" ");
}//for
printf("顶点（事件）");
for(int i = 0; i < count - count / 2; i++) {
printf(" ");
}//for
printf("|\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
}//printhead
/*
函数：printi
参数：ALGraph G 图G（邻接表表示）
返回值：无
作用：以表格形式打印i
*/
void printi(ALGraph G) {
printf("| i |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %2d |", i);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
}//printi
/*
函数：printvex
参数：ALGraph G 图G（邻接表表示）
返回值：无
作用：以表格形式打印顶点名称
*/
void printvex(ALGraph G) {
printf("| 顶点 |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %2d |", G.vertices[i]);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
}//printvex
/*
函数：printve
参数：ALGraph G 图G（邻接表表示）
int ve[] 事件的最早发生时间ve[]
返回值：无
作用：以表格形式打印ve名称
*/
void printve(ALGraph G, int ve[]) {
printf("| ve |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %2d |", ve[i]);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
}//printve
/*
函数：printvl
参数：ALGraph G 图G（邻接表表示）
int vl[] 事件的最晚发生时间vl[]
返回值：无
作用：以表格形式打印ve名称
*/
void printvl(ALGraph G, int vl[]) {
printf("| vl |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %2d |", vl[i]);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
}//printvl
/*
函数：printCritical1
参数：ALGraph G 图G（邻接表表示）
int ve[] 事件的最早发生时间ve[]
int vl[] 事件的最晚发生时间vl[]
返回值：无
作用：以表格形式打印顶点是否在关键路径上
*/
void printCritical1(ALGraph G, int ve[], int vl[]) {
printf("| 关键路径 |");
for(int i = 0; i < G.vexnum; i++) {
//在关键路径上的顶点加√标记
if(ve[i] == vl[i]) {
printf(" √ |");
}//if
else {
printf(" |");
}//else
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
}//printCritical1源文件：关键路径测试.cpp
//**************************引入头文件*****************************
#include <stdio.h> //使用了标准库函数
#include <stdlib.h> //使用了动态内存分配函数
#include "my_constants.h" //引入自定义的符号常量，主要是状态码
#include "ALGraph.h" //引入图的邻接表存储结构定义
#include "LinkedList.cpp" //引入单链表实现，用到其中的插入、删除等操作
#include "ALGraph.cpp" //引入图的邻接表存储结构基本操作实现
#include "Stack.cpp" //引入顺序栈的基本操作实现
#include "CriticalPath.cpp" //引入图的关键路径算法实现
int main() {
printf("----------------图的关键路径（邻接表）演示程序------------------\n\n");
//图的邻接表存储方式
ALGraph G;
//创建图g并打印初始状态
printf("->测试图G的创建：(关键路径需要图的类型为有向网，请输入1)\n");
CreateGraph(G);
printf("图G创建成功！\n");
printf("->打印创建后的图G：\n");
Display(G);
//测试拓扑排序
printf("\n->关键路径计算结果：\n");
CriticalPath(G);
//测试销毁图G
printf("\n->测试销毁图G:");
DestroyGraph(G);
printf("销毁成功！");
printf("演示结束");
}//main我们使用这张AOE网作为输入来测试关键路径算法的正确性（顶点多一点）： 
这张AOE网的关键路径应该是：v1 -> v3 -> v5 -> v8 -> v9 -> v10 -> v11。读者可以自行手工写出关键路径验证其正确性。
程序运行过程中的输入和输出如下：
----------------图的关键路径（邻接表）演示程序------------------
->测试图G的创建：(关键路径需要图的类型为有向网，请输入1)
请输入图的类型(有向图输入0, 有向网输入1,无向图输入2,无向网输入3): 1
请输入图的顶点数,边数: 11,15
请输入11个顶点的值(用空格隔开):
1 2 3 4 5 6 7 8 9 10 11
请输入每条弧(边)的弧尾、弧头和权值(以逗号作为间隔):
1,2,3
1,3,4
2,4,2
2,5,1
3,5,3
3,6,5
4,7,6
5,7,8
5,8,4
6,9,2
7,11,7
8,10,4
8,9,10
9,10,1
10,11,6
图G创建成功！
->打印创建后的图G：
此图为有向网!
图*有11个顶点，15条弧(边)，它们分别是：
+----+-----------------------------------------------
|顶点| 邻接顶点(和权值)
+----+-----------------------------------------------
| 1 | →3 ,权值:4 →2 ,权值:3
+----+-----------------------------------------------
| 2 | →5 ,权值:1 →4 ,权值:2
+----+-----------------------------------------------
| 3 | →6 ,权值:5 →5 ,权值:3
+----+-----------------------------------------------
| 4 | →7 ,权值:6
+----+-----------------------------------------------
| 5 | →8 ,权值:4 →7 ,权值:8
+----+-----------------------------------------------
| 6 | →9 ,权值:2
+----+-----------------------------------------------
| 7 | →11 ,权值:7
+----+-----------------------------------------------
| 8 | →9 ,权值:10 →10 ,权值:4
+----+-----------------------------------------------
| 9 | →10 ,权值:1
+----+-----------------------------------------------
| 10 | →11 ,权值:6
+----+-----------------------------------------------
| 11 |
+----+-----------------------------------------------
->关键路径计算结果：
->求得的拓扑序列：1 2 4 3 5 7 8 6 9 10 11
->通过拓扑排序，图中没有环！
+----------------------------------------------------------------------------+
| 顶点（事件） |
+----------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
+----------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
+----------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| ve | 0 | 3 | 4 | 5 | 7 | 9 | 15 | 11 | 21 | 22 | 28 |
+----------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| vl | 0 | 6 | 4 | 15 | 7 | 19 | 21 | 11 | 21 | 22 | 28 |
+----------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 关键路径 | √ | | √ | | √ | | | √ | √ | √ | √ |
+----------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
+------+------+------+------+------+----------+
| 活动（边） |
+------+------+------+------+------+----------+
| 弧尾 | 弧头 | 权值 | ee | el | 关键活动 |
+------+------+------+------+------+----------+
| 1 | 3 | 4 | 0 | 0 | √ |
+------+------+------+------+------+----------+
| 1 | 2 | 3 | 0 | 3 | |
+------+------+------+------+------+----------+
| 2 | 5 | 1 | 3 | 6 | |
+------+------+------+------+------+----------+
| 2 | 4 | 2 | 3 | 13 | |
+------+------+------+------+------+----------+
| 3 | 6 | 5 | 4 | 14 | |
+------+------+------+------+------+----------+
| 3 | 5 | 3 | 4 | 4 | √ |
+------+------+------+------+------+----------+
| 4 | 7 | 6 | 5 | 15 | |
+------+------+------+------+------+----------+
| 5 | 8 | 4 | 7 | 7 | √ |
+------+------+------+------+------+----------+
| 5 | 7 | 8 | 7 | 13 | |
+------+------+------+------+------+----------+
| 6 | 9 | 2 | 9 | 19 | |
+------+------+------+------+------+----------+
| 7 | 11 | 7 | 15 | 21 | |
+------+------+------+------+------+----------+
| 8 | 9 | 10 | 11 | 11 | √ |
+------+------+------+------+------+----------+
| 8 | 10 | 4 | 11 | 18 | |
+------+------+------+------+------+----------+
| 9 | 10 | 1 | 21 | 21 | √ |
+------+------+------+------+------+----------+
| 10 | 11 | 6 | 22 | 22 | √ |
+------+------+------+------+------+----------+
->测试销毁图G:销毁成功！演示结束
--------------------------------
Process exited with return value 0
Press any key to continue . . .总结：
关键路径解决的是工程进度安排的问题，找出关键路径并对路径上的活动进行处理可以加快工程进度。有的工程关键路径可能不止一条，只加快一条关键路径上的活动是可能没用的，这就需要加快多条关键路径上的活动。活动被加快之后，关键路径可能会发生变化，原来不在关键路径上的事件和活动有可能出现在关键路径上。
图这一章最后一个程序到此就结束了。下次的文章会介绍第九章的第一个程序——顺序表和有序表的查找算法的实现。感谢大家一直以来的关注和支持。再见！