1.AOE网

　　一个带权的有向无环图，顶点表示事件，弧表示活动，权表示活动持续的时间。通常AOE网用来估算工程的完成时间。

　　例如：

　　　　

　　　　上图是一个假想的有11项活动的AOE网，有9个事件，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如V₄表示a₃已经完成，a₆可以开始。

　　　通常整个工程只有一个入度为零的点（源点）和一个出度为零的点（汇点）。

　　　也许你可以定义一个工程或者一件事有多个初始态，或者多个结束态，但那增加了问题的复杂性，不是最小意义的分割，为了方便研究一般把某件事分清楚，再定义一个个事件和活动。

　　　AOE网中有些活动可以并行进行，如图中的a₂和a_5，若某个活动早已完成，另一个活动还未开始，则这个工程不能算结束。也许你会脑洞大开，先完成的人不可以帮助那些做的慢的人嘛，当然可以，只是那样就不再是我们初始定义时的AOE网，现实中分工明确，每个团队或者个体都有自己的任务，一般独立完成，所以工程完成的最早时间是从开始点到完成点的最长路径的长度。额，注意一下，路径长度不是弧的个数而是弧所代表的活动的持续时间。也许你还会想，如果那些做的慢的人再一次放缓进度，那活动持续时间不是更长了么，额，这个嘛，犯了一个逻辑上的错误。我们在规划时必须有一些确定的值，如果什么规划时连预估的范围都是不确定的，那估算也没有任何意义或者说根本无法进行。

　　　假设我们已经估算了某个工程设计到的所有活动的持续时间，那么工程完成的最短时间就是最长路径的长度，称之为关键路径。

　　　为了便于描述，我们定义一些符号：

　　　 e(i)表示活动a_i的最早开始时间

　　　 l(i)表示活动a_i的最迟开始时间，就是在不推迟整个工程的前提下，某个活动最迟必须开始时间（这个概念好像有点抽象，你想，一个团队中有些人做的快有些人做的慢，做的快的人就可以稍做休息，只需要不在慢的人之后做完就可以了，心疼那些做的慢的人，没有休息）

　　   l(i)-e(i)表示活动a_i的时间余量

　　　l(i)=e(i)的活动称之为关键活动

　　　例如活动a₅的最早开始时间是4，最迟开始时间是5

　　　那么如何辨别关键路径呢？

　　　关键路径嘛，就是不能再拖拉的活动了，否则本来就因为该活动完成速度较慢而延长的工程完成时间会更长。也就是做关键路径上的活动的人不能中途休息，也就是最早开始时间和最迟开始时间一致。那么如何求  l(i)和e(i)。这时候你应该回忆AOE网中事件的定义：若到达某个顶点则表示它前面的活动已经完成，以这个顶点为弧尾的弧才可以开始。这点不难理解，如果你们要做一个电子标签系统，做客户端界面和后端数据库的人总得等做驱动的人提供接口。所以我们可以先求事件最早发生时间ve(j)和最迟发生时间vl(j),如果活动a_i由弧<j,k>表示，其持续时间记为dut(<j,k>)，则有如下关系：

　　e(i)=ve(j)

　　l(i)=vl(k)-dut(<j,k>)

　　求ve(j)和vl(j)分两步：

　  ⑴从ve(0)=0开始向前递推

　　　　　　ve(j)=Max{ve(i)+dut(<i,j>)}　　　　<i,j>∈T，j=1,2,...,n-1  　　T是所有以第j个顶点为弧头的弧的集合

　　　　　　PS:所谓的第j个顶点不过是我们存储图是给顶点标的序号；求最早开始时间嘛，要等最慢的那个活动完成才可以开始，所以就求在j顶点的所有直接前驱加上到第j个顶点的时间中完成的最长的那个；也许你会问那前驱的前驱怎么办，其实这里反应了一个算法思想，动态规划。我们可以简单用个反证法证明一下在这里的正确性。

　　　　　　假设前驱记录的最早时间不是最早时间，也就是说存在从开始点到该店的更长路径，然而，这个不可能的，从定义可以知道，我们在求最早时间过程中每次都是选的最长路径，如果存在从开始点到该点的更长路径，便与我们的构造定义矛盾，所以前驱记录的最早时间是最早时间。

   (2)从vl(n-1)=ve(n-1)起向后递推

　　　　vl(i)=Min{vl(j)-dut(<i,j>)}  <i,j>∈S　　S是所有以第i个顶点为弧尾的弧的集合

　　　　 PS:从结束点开始（工程完成的时间，也就是最长路径长度），对于某个事件，求最迟开始时间嘛，你想一下这个事件代表前面（前驱）活动的已经完成，后面（后继）的才可以开始。那么这个事件的最迟发生时间加上到直接后继的时间不能超过直接后继的最迟发生时间，如果超过了，直接后继就要继续延迟。本来就拖了，再拖了，工程的时间只会更长，也就是你即使做的快，也不能无限等，总得有个限度。那么这个限度是什么呢，你要保证以你的工作为基础做的最慢的人（直接后继）能够在下一个事件的最迟时间之前（可以等于）完成。所以你地预留最的最慢的人的工作时间（活动时间）。

2.具体编码实现

　　从上述分析可知，要求某个事件的最早发生时间，就必须先求得其所有前驱的最早发生时间，那么问题又来了，怎么求某个事件的前驱，这就要用到拓扑排序了；

　　 要求某个事件的最迟发生时间，就必须先求得其所有后继的最迟发生时间，怎么求某个事件的后继呢，用逆拓扑排序就可以了，也就是拓扑序列反过来。

　　 

#include
     
      #include
      
       typedef struct _arcNode{    int adjvex;    int weight;    struct _arcNode *nextarc;}arcNode;//定义有向弧，包含弧头标号，弧的权重（活动持续时间）typedef struct  _vNode{    char data;    arcNode *firstarc;}vNode;//定义顶点，包含顶点信息，指向以该顶点为弧尾的第一条弧#define  MaxVertexNum 100//最大顶点数typedef vNode adjList[MaxVertexNum];typedef struct _adjGraph{    adjList ver;    int e, n;}adjGraph;//定义邻接表void createAdjGraph(adjGraph *G){    scanf("%d,%d", &G->n, &G->e);    getchar();    for (int i = 0; i < G->n; i++)    {        scanf("%c ", &G->ver[i].data);        G->ver[i].firstarc = NULL;    }    int a, b, w;    for (int i = 0; i < G->e; i++)    {        scanf("%d,%d,%d", &a, &b, &w);        arcNode *tmp = (arcNode*)malloc(sizeof(arcNode));        tmp->weight = w;        if (G->ver[a].firstarc == NULL)        {            tmp->adjvex = b;            tmp->nextarc = NULL;            G->ver[a].firstarc = tmp;        }        else        {            tmp->adjvex = b;            tmp->nextarc = G->ver[a].firstarc;            G->ver[a].firstarc = tmp;        }    }}//创建邻接表typedef struct  _topoSequenceS{    int verNum[MaxVertexNum];    int top;}topoSequenceS;//定义拓扑排序的存储结构，拓扑排序时，先输出的顶点标号入栈；你拓扑排序倒过来就可以topoSequenceS *topoS = (topoSequenceS*)malloc(sizeof(topoSequenceS));void findInDegree(adjGraph *G, int *indegree){    for (int i = 0; i < G->n; i++)    {        arcNode *arcPos = G->ver[i].firstarc;        while (arcPos != NULL)        {            indegree[arcPos->adjvex] += 1;            arcPos = arcPos->nextarc;        }    }}//查询每个顶点的入度，indegree的下标对应顶点标号；搜索时每遇到以某个顶点为弧头的弧对应弧头的入度就加一bool  topologicalSort(adjGraph *G,int *ve){    int *indegree = (int*)malloc(sizeof(int)*G->n);    for (int i = 0; i < G->n; i++)        indegree[i] = 0;//初始化每个顶点的入度    findInDegree(G, indegree);    int *tmpS = (int*)malloc(sizeof(int)*G->n);//临时存储入度为零且未输出的顶点    int top = -1;    for (int i = 0; i < G->n; i++)    {        if (!indegree[i])tmpS[++top] = i;    }    for (int i = 0; i < G->n; i++)        ve[i] = 0;//初始化每个顶点的最早开始时间    topoS->top = -1;//初始化存储拓扑序列的栈    int i = 0;    while (top != -1)//拓扑排序    {        i = topoS->verNum[++topoS->top] = tmpS[top--];//入度为零，弹出，也就是输出对应顶点        arcNode *arcPos = G->ver[i].firstarc;        while (arcPos != NULL)//遍历所有以顶点i为弧尾的弧        {            if (!(--indegree[arcPos->adjvex]))tmpS[++top] = arcPos->adjvex;//所有以顶点i为直接前驱的顶点的入度减一            if (ve[i] + arcPos->weight > ve[arcPos->adjvex])ve[arcPos->adjvex] = ve[i] + arcPos->weight;//求所有以顶点i为直接前驱的顶点的最早开始时间            /*            貌似与前面求事件最早发生时间ve(j)和最迟发生时间vl(j)不同，实则一样，            因为在拓扑排序过程，会遍历到所有的弧，每次记录某个顶点（arcPos->adjvex）最早开始时间的，结束时存储的就是最大的，                        */            arcPos = arcPos->nextarc;        }    }    if (topoS->top < G->n - 1)return false;//有回路    else        return true;}bool criticalPath(adjGraph *G){    int *ve = (int*)malloc(sizeof(int)*G->n);//定义存储顶点最早开始时间数组    int *vl = (int*)malloc(sizeof(int)*G->n);//定义存储顶点最迟开始时间数组    if (!topologicalSort(G, ve))return false;//拓扑排序，并求出ve    for (int i = 0; i < G->n; i++)    {        vl[i] = ve[G->n - 1];    }//初始化所有顶点的最迟开始时间，设为最长路径长度    int j = 0;    while (topoS->top != -1)    {        j = topoS->verNum[topoS->top--];//你拓扑排序输出        printf("\n%c\n", G->ver[j].data);        arcNode *arcPos = G->ver[j].firstarc;        while (arcPos != NULL)//遍历所有以j为弧尾的弧        {            if (vl[arcPos->adjvex] - arcPos->weight < vl[j])                vl[j] = vl[arcPos->adjvex] - arcPos->weight;//记录j的最迟开始时间                                                            /*                                                            貌似与前面求事件最早发生时间ve(j)和最迟发生时间vl(j)不同，实则一样，                                                            因为在拓扑排序过程，会遍历到所有的弧，每次记录某个顶点（j）最迟开始时间的，结束时存储的就是最小的，                                                            */            arcPos = arcPos->nextarc;        }    }    int ee = 0; int el = 0;    for (int i = 0; i < G->n; i++)    {        arcNode *arcPos = G->ver[i].firstarc;        while (arcPos != NULL)        {            ee = ve[i];//活动
       
        adjvex>的最早开始时间            el = vl[arcPos->adjvex] - arcPos->weight;//活动
        
         adjvex>的最迟开始时间            if (ee == el)printf("%c--%c:%d\n", G->ver[i].data, G->ver[arcPos->adjvex].data, arcPos->weight);            arcPos = arcPos->nextarc;        }    }}#include
         
          int main(void){    freopen(".\\in.txt", "r", stdin);    adjGraph *G = (adjGraph*)malloc(sizeof(adjGraph));    createAdjGraph(G);    fclose(stdin);    for (int i = 0; i < G->n; i++)    {        printf("%c->", G->ver[i].data);        arcNode *pos = G->ver[i].firstarc;        while (pos != NULL)        {            printf("%c->", G->ver[pos->adjvex].data);            pos = pos->nextarc;        }        printf("\n");    }//输出文本中存储的图邻接表        if (!criticalPath(G))        printf("Error!There is a circuit!\n");        getch();    return 0;}
         
        
       
      
     

 

 

 

测试文本（记录信息描述的就是本文第一个图）

9,11

1 2 3 4 5 6 7 8 9

0,1,6

0,2,4

0,3,5

1,4,1

2,4,1

3,5,2

4,6,9

4,7,7

5,7,4

6,8,2

7,8,4

测试结果：

　　

　　打印邻接表

　　

　打印拓扑排序输出和关键活动