AOE网：
在一个表示工程的带权有向图中，用顶点表示事件，用有向边上的权值表示活动表示持续时间，这种有向图的边表示活动的网，我们称为AOE网（Activity On Edge Network）。
我们把AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。
——etv（Earliest Time Of Vertex）
事件最早发生时间，就是顶点的最早发生时间。
——ltv （Latest Time Of Vertex）
事件最晚发生时间，就是每个顶点对应的事件最晚需要开始的时间，如果超出此时间将会延误整个工期。
——ete （Earliest Time Of Edge）
活动的最早开工时间，就是弧的最早发生时间。
——lte （Latest Time Of Edge）
活动的最晚发生时间，就是不推迟工期的最晚开工时间。
#define <stdio.h>
//边表结点声明
typedef struct EdgeNode
{int adjvex;struct EdgeNode * next;
}EdgeNode;//顶点表结点声明
typedef struct VertexNode
{int in; //顶点入度 int data;EdgeNode * firstedge;
}VertexNode,AdjList[MAXVEX];typedef struct
{AdjList adjList;int numVertexes,numEdges;
}graphAdjList , *GraphAdjList;int *etv,*ltv;
int *stack2; //用于存储拓扑序列的栈
int top2; //用于stack2的栈顶指针 //拓扑排序算法
//若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERRor
Status TopologicalSort(GraphAdjList GL)
{EdgeNode *e;int i,k,gettop;int top = 0; //用于栈指针下标索引 int count = 0; //用于统计输出顶点的个数 int *stack; //用于存储入度为0的顶点stack = (int *)malloc(GL->numVertexes * sizeof(int));for(i=0;i < GL->numVertexes;i++){if(0 == GL->adjList[i].in){stack[++top] = i; //将度为0的顶点下标入栈 }} //初始化etv都为0top2 = 0;etv = (int *)malloc(GL->numVertexes * sizeof(int));for(i=0;i < GL->numVertexes * sizeof(int)){etv[i] = 0;} stack2 = (int *)malloc(GL->numVertexes * sizeof(int));while(0 != top){gettop = stack[top--]; //出栈 stack2[++top2] = gettop; //保存拓扑序列顺序 count++;for(e = GL->adjList[gettop].firstedge;e;e=e->next){k = e->adjvex;//将k号顶点邻接点的入度-1，因为他的前驱已经消除//接着判断-1后入度是否为0，如果为0则也入栈 if(!(--GL->adjList[k].in)){stack[++top] = k;}if((etv[gettop]+e->weight) > etv[k]){etv[k] = etv[gettop] + e->weight;} }} if(count <GL->numVertexes ) //如果count小于顶点数，说明存在环{return ERROR;} else{return OK;}
}//求关键路径，GL为有向图，输出GL的各项关键活动
void CriticalPath(GraphAdjList GL)
{EdgeNode *e;int i,gettop,k,j;int ete,lte;TopologicalSort(GL);ltv = (int *)malloc(GL->numVertexes * sizeof(int));for(i=0;i<GL->numVertexes;i++){ltv[i] = etv[GL->numVertexes-1];}//从汇点倒过来逐个计算ltv while(0 !=top2){gettop = stack2[top2--]; //第一个出栈是汇点 for(e = GL->adjList[gettop].firstedge; e ;e=e->next){k = e->adjvex;if((ltv[k]- e->weight) < ltv[gettop]){ltv[gettop] = ltv[k] - e->weight;}}}//通过etv和ltv求ete和lte for(j=0;j<GL->numVertexes;j++){for(e = GL->adjList[j].firstedge; e; e = e->next){k = e->adjvex;ete = etv[j];lte = ltv[k] - e->weight;if(ete == lte){printf("<v%d,v%d> length: %d , ",GL->adjList[j].data,GL->adjList[k].data,e->weight);}}}} 
