- 顶点下标查找函数（LocateVex）
- 创建有向网的邻接表（CreateDN）
- 邻接表打印函数（print）
- 拓扑排序（TopologicalSort）
- 关键路径（CriticalPath）
AOV网与AOE网的实例：
- 问题描述：请问汽车厂制造一辆汽车，最短需要多少天？ 其中生产一个轮子：0.5天；发动机：2天；底盘：2天；外壳：2天；其他零部件：2天；全部配件生产完毕之后，将所有零件集中在一起需要0.5天，组装起来需要2天。
- 通过实例我们了解到，AOV网与AOE网的处理问题方式有所不同，它们顶点与边之间所描述的对象及其对象关系也不同
- AOE网与关键路径：由AOE网的图示我们可以看出，汽车制造的时间，由图示中的红色箭头控制，因为红色箭头这一流程，是耗时最长的，要是能降低这一流程的耗时，那么整个汽车制造时间也得以降低，所以这条红色箭头所指是的流程，我们就称之为关键路径（Critical Path）。
- 最短工期就等于最长路径（关键路径）
- 所以我们要降低汽车制造的工期，需要从流程图中找到关键路径（Critical Path），降低关键路径所消耗的时间，就能缩短这项工程的工期。
关键路径四要素：
- 顶点（vi）代表时间；边（ai）代表活动；边上的权值（w）代表活动持续时间。
- 时间余量：我们用"造外壳（2天）"、"造发动机（3天）"为例子，首先我们知道，“造外壳”、“造发动机”、“造轮子”、“造底盘”、"造其他零件"都属于制造工艺。我们要先完成所有的制造工艺，才能进行下一步的组装工艺。其中"造发动机"时间最长为3天，其他制造工艺工期均为2天，那么也就是说整个制造工艺的时间要3天才能完成。意思就是说，所有制造工艺只要在3天之内完成即可。假设1号开工，要在3号完工（1号、2号、3号三天），那么对于"造外壳"而言，只需要在2天之内完成工作即可，可以1号开工2号完工，也可以2号开工3号完工，这时候"造外壳"的时间余量为1天，其最晚开始时间可以是2号；那如果是"造发动机"呢？只能在1号开工，不然无法在3号完工，所以"造发动机"的时间余量为0天，最晚开始时间只能是1号。
-
事件vi的最早发生时间ve(i)：事件vi的最早发生时间是等待vi之前的所有活动都完成，所以ve(i)是从源点到vi的最长路径长度。起始点（源点）的最早发生时间为0。（vk是vi的前驱事件）
所以可以推出：
ve(0) = 0;（源点的最早发生时间为0）
i∈[1,n]时，ve(i) = Max{ ve(k) + weight（k->i）} ; -
事件vi的最晚发生时间vl(i)：不拖延工期的前提下，事件vi被允许的最晚发生时间。（vk是vi的后续事件）活动ai=<vi,vk>,vi的最晚发生时间，取决于这个活动被允许的最晚结束时间，而所被允许的最晚结束时间也正是vk的最晚开始时间，也就是vl（k），所以我们就得到等式:
最晚发生时间vl（i）+ 活动持续时间weight = 最晚结束时间vl（k）
所以可以推出：
vl(n-1) = ve(n-1);（汇点的最早发生时间与最晚发生时间相等）
i∈[0,n-2]时，vl(i) = Min{ vl(k) - weight（i->k）} ; -
活动ai=<vj,vk>的最早开始时间e(i)：只有事件vj发生了，活动ai才能开始。所以活动ai的最早开始时间正是时间vj的最早发生时间ve(j)。
e（i）=ve（j）; -
活动a i=<vj,vk>的最晚开始时间l(i)：由2可得：活动ai的最晚开始时间， 取决于活动被允许的最晚结束时间，而被允许的最晚结束时间也正是vk的最晚开始时间，也就是vl（k），所以我们就得到等式:
最晚开始时间l（i）+ 活动持续时间weight = 最晚结束时间vl（k）
所以推出：
l(i)=vl(k)-weight(j->k);
如何求出关键路径？
- 求出事件最早发生时间ve[i]：顺拓扑序
- 求出事件最晚发生时间vl[i]：逆拓扑序
- 通过ve[i]和vl[i]计算出活动最早开始时间（e） 与 活动最晚开始时间（l）
- 若
e(i)==l(i)则当前i所指向的活动是关键活动（Critical Activity）
- 对于上图6.28求关键路径：
为什么当e(i)==l(i)时，就是关键活动？
- 当活动最晚开始时间等于活动最早开始时间，那么也就是说时间余量为0，说明这个活动无法推迟或延期的余地（否则会延误工程时间进度），所以该活动是否能按期完工决定了整个工程是否能按期完成，所有的关键活动连起来，就是关键路径。
CriticalPath算法步骤：
- （未完待续）
void CriticalPath(ALGraph *G)
{
int i;
int j,k;// <Vj,Vk>
int e,l;//活动最早开始时间/活动最晚开始时间
int topo[VertexMax];//拓扑数组，用于存储拓扑排序结果（存储内容是每个结点的坐标）
int ve[VertexMax]; //事件vi的最早发生时间
int vl[VertexMax]; //事件vi的最晚发生时间
struct ArcNode *p;
//1.调用拓扑排序，检测图是否存在环
if(!TopologicalSort(G,topo))//若拓扑排序成功，topo数组也将处理完毕
return;
//2.正拓扑排序，求出事件最早发生时间
for(i=0;i<G->vexnum;i++)
ve[i]=0;//所有ve都初始化为0
for(i=0;i<G->vexnum;i++)
{
j=topo[i];//j为起始点，k为终点
p=G->AdjList[j].firstarc;//用指针p去依次寻找j的每一个邻接点
while(p)
{
k=p->adjvex;
if(ve[k]<ve[j]+p->weight)//根据j的邻接点k，不断更新ve[]的值（选出最大值，原理类似于选择排序）
{
ve[k]=ve[j]+p->weight;
}
p=p->next;
}
}
//3.逆拓扑排序，求出事件最迟发生时间
for(i=0;i<G->vexnum;i++)
vl[i]=ve[G->vexnum-1];//所有vl都初始化为ve[G->vexnum-1]
for(i=G->vexnum-1;i>=0;i--)
{
j=topo[i];
p=G->AdjList[j].firstarc;//让p去依次查找邻接点
while(p)
{
k=p->adjvex;
if(vl[j]>vl[k]-p->weight)//根据j的邻接点k，不断更新vl[]的值（选出最小值，原理类似于选择排序）
{
vl[j]=vl[k]-p->weight;
}
p=p->next;
}
}
//4.计算e和l，通过判断e是否等于l确定该活动是否是关键活动，从而确定关键路径
for(i=0;i<G->vexnum;i++)
{
p=G->AdjList[i].firstarc;//让p去依次查找邻接点
while(p)
{
j=p->adjvex;
e=ve[i];//计算活动最早开始时间 e
l=vl[j]-p->weight;//计算活动最晚开始时间 l
if(e==l)//如果e=l，说明该活动是关键活动
{
//把每个关键活动输出，即是关键路径
printf("\t%c->%c(%d)\n",G->AdjList[i].vertex,G->AdjList[j].vertex,p->weight);
}
p=p->next;
}
}
}
时间复杂度分析：
- 算法的2、3、4部分循环结构一致，都使用二重循环，相当于把整个邻接表的所有顶点和边都扫描一遍，所以时间复杂度为O（n+e）
完整源代码：
#include <stdio.h>
#include <stdlib.h>
#define VertexType char //顶点的数据类型（char）
#define VertexMax 20 //最大顶点个数
typedef struct ArcNode//边表
{
int adjvex;//存储的是该顶点在顶点数组即AdjList[]中的位置
int weight;//权值
struct ArcNode *next;
}ArcNode;
typedef struct VNode //顶单个点
{
VertexType vertex;
struct ArcNode *firstarc;
}VNode;
typedef struct //顶点表
{
VNode AdjList[VertexMax];//由顶点构成的结构体数组
int vexnum,arcnum; //顶点数和边数
}ALGraph;
int LocateVex(ALGraph *G,VertexType v)
{
int i;
for(i=0;i<G->vexnum;i++)
{
if(v==G->AdjList[i].vertex)
{
return i;
}
}
printf("No Such Vertex!\n");
return -1;
}
//有向图
void CreateDN(ALGraph *G)
{
int i,j;
//1.输入顶点数和边数
printf("输入顶点个数和边数：\n");
printf("顶点数 n=");
scanf("%d",&G->vexnum);
printf("边 数 e=");
scanf("%d",&G->arcnum);
printf("\n");
printf("\n");
//2.顶点表数据域填值初始化顶点表指针域
printf("输入顶点元素(用空格隔开)：");
for(i=0;i<G->vexnum;i++)
{
scanf(" %c",&G->AdjList[i].vertex);
G->AdjList[i].firstarc=NULL;
}
printf("\n");
//3.输入边信息构造邻接表
int n,m;
VertexType v1,v2;
int weight;
ArcNode *p1,*p2;
printf("请输入边的信息：\n\n");
for(i=0;i<G->arcnum;i++)
{ //输入边信息，并确定v1和v2在G中的位置，即顶点在AdjList[]数组中的位置（下标）
printf("输入第%d条边信息：",i+1);
scanf(" %c%c,%d",&v1,&v2,&weight);
n=LocateVex(G,v1);
m=LocateVex(G,v2);
if(n==-1||m==-1)
{
printf("NO This Vertex!\n");
return;
}
p1=(ArcNode *)malloc(sizeof(ArcNode));
p1->adjvex=m;//填上坐标
p1->weight=weight;//填上权值
p1->next=G->AdjList[n].firstarc;//改链（头插法）
G->AdjList[n].firstarc=p1;
}//for
}
void print(ALGraph G)
{
int i;
ArcNode *p;
printf("\n-------------------------------");
printf("\n图的邻接表表示：\n");
for(i=0;i<G.vexnum;i++)
{
printf("\n AdjList[%d]%4c",i,G.AdjList[i].vertex);
p=G.AdjList[i].firstarc;
while(p!=NULL)
{
printf("-->%d(%d)",p->adjvex,p->weight);
p=p->next;
}
}
printf("\n");
printf("\n-------------------------------\n");
}
int TopologicalSort(ALGraph *G,int *topo)
{
int i;
int top=-1;//栈顶指针
int Gettop;//用于存储/获取栈的栈顶元素
int count=0;//用于统计拓扑排序生成的结点数（若生成结点数 < 图的结点数，则代表图中有环，拓扑排序不成功）
int stack[VertexMax]={0};//栈
int indegree[VertexMax]={0};//入度数组
struct ArcNode *p;//临时变量
//1.计算顶点入度，并存入indegree数组中
for(i=0;i<G->vexnum;i++)
{
if(G->AdjList[i].firstarc!=NULL)
{
p=G->AdjList[i].firstarc;
while(p!=NULL)
{
indegree[p->adjvex]++;
p=p->next;
}
}
}
//2.初始化部分：将初始入度为0的顶点入栈
for(i=0;i<G->vexnum;i++)
{
if(indegree[i]==0)
{
stack[++top]=i;//先将指针加一在进行存储
}
}
//3.拓扑排序
int m=0;
while(top!=-1)//栈不为空
{
Gettop=stack[top--];//获取栈顶元素，并且栈顶指针减一
topo[m++]=Gettop;
//printf(" %c(%d)",G->AdjList[Gettop].vertex,topo[m-1]);//输出栈顶元素
count++;
p=G->AdjList[Gettop].firstarc;
while(p!=NULL)
{
indegree[p->adjvex]--;
if(indegree[p->adjvex]==0)
{
stack[++top]=p->adjvex;
}
p=p->next;
}
}
//4.判断拓扑排序是否成功（生成结点数 < 图的结点数，则代表图中有环，拓扑排序不成功）
if(count<G->vexnum)
{
printf("TopologicalSort Failed!\n");
return 0; //拓扑排序失败
}
else
return 1; //拓扑排序成功
}
void CriticalPath(ALGraph *G)
{
int i;
int j,k;// <Vj,Vk>
int e,l;//活动最早开始时间/活动最晚开始时间
int topo[VertexMax];//拓扑数组，用于存储拓扑排序结果（存储内容是每个结点的坐标）
int ve[VertexMax]; //事件vi的最早发生时间
int vl[VertexMax]; //事件vi的最晚发生时间
struct ArcNode *p;
//1.调用拓扑排序，检测图是否存在环
if(!TopologicalSort(G,topo))//若拓扑排序成功，topo数组也将处理完毕
{
return;
}
//2.正拓扑排序，求出事件最早发生时间
for(i=0;i<G->vexnum;i++)
ve[i]=0;
for(i=0;i<G->vexnum;i++)
{
j=topo[i];//j为起始点，k为终点
p=G->AdjList[j].firstarc;//用指针p去依次寻找j的每一个邻接点
while(p)
{
k=p->adjvex;
if(ve[k]<ve[j]+p->weight)//根据j的邻接点k，不断更新ve[]的值（选出最大值，原理类似于选择排序）
{
ve[k]=ve[j]+p->weight;
}
p=p->next;
}
}
//3.逆拓扑排序，求出事件最迟发生时间
for(i=0;i<G->vexnum;i++)
vl[i]=ve[G->vexnum-1];
for(i=G->vexnum-1;i>=0;i--)
{
j=topo[i];
p=G->AdjList[j].firstarc;//让p去依次查找邻接点
while(p)
{
k=p->adjvex;
if(vl[j]>vl[k]-p->weight)//根据j的邻接点k，不断更新vl[]的值（选出最小值，原理类似于选择排序）
{
vl[j]=vl[k]-p->weight;
}
p=p->next;
}
}
//输出ve[i]
printf("\tve[i]:");
for(i=0;i<G->vexnum;i++)
{
printf("\t%d",ve[i]);
}
printf("\n");
//输出vl[i]
printf("\tvl[i]:");
for(i=0;i<G->vexnum;i++)
{
printf("\t%d",vl[i]);
}
printf("\n\n");
//4.计算e和l，通过判断e是否等于l确定该活动是否是关键活动，从而确定关键路径
for(i=0;i<G->vexnum;i++)
{
p=G->AdjList[i].firstarc;//让p去依次查找邻接点
while(p)
{
j=p->adjvex;
e=ve[i];//计算活动最早开始时间 e
l=vl[j]-p->weight;//计算活动最晚开始时间 l
if(e==l)//如果e=l，说明该活动是关键活动
{
printf("\t%c->%c(%d)\n",G->AdjList[i].vertex,G->AdjList[j].vertex,p->weight);
}
p=p->next;
}
}
}
int main()
{
ALGraph G;
CreateDN(&G);
print(G);
printf("关键路径：\n\n");
CriticalPath(&G);
return 0;
}
执行结果：
（注：用0代表V0,1代表V1，以此类推。）
参考：
1.AOV网与AOE网的实例部分文图参考自：懒猫老师
2.参考教材：严蔚敏数据结构（C语言第二版）
