声明：图片及内容基于https://www.bilibili.com/video/BV1BZ4y1T7Yx?from=articleDetail
原理 AOE网
关键路径
数据结构
核心代码
TopologicalSort
/* TopologicalSort用于实现拓扑排序 参数：result用来保存处理过的拓扑排序顶点；count用来保存处理过的拓扑排序顶点的个数 功能：进行拓扑排序，将找到的拓扑顶点序号存入result数组（result可以看成一个栈,count可以看成是栈顶指针） 增加的功能：用注释=====标识，在拓扑排序的同时计算ve数组的值[事件最早发生时间] */ bool ALGraph ::TopologicalSort(int result[], int &count){ int stack[MAX_VERTEX]; //把顶点对应的下标压入堆栈 int top = -1; int inVex; //用来保存从堆栈中弹出的顶点（下标）[书上的j，代表一个边的起始顶点] int outVex;//遍历一个顶点的所有邻接边结点时,用outVex暂存当前处理的顶点[书上的k，代表一个边的终止顶点] ArcNode *p; //初始化事件最早发生时间ve数组===== for(int i=0;i<vertexNum;i++){ ve[i]=0; } //遍历顶点表，把入度为0的压栈 for(int i=0;i<vertexNum;i++){ if(adjList[i].in==0){ stack[++top]=i; } } //完成拓扑排序 count=0; while(top!=-1){ inVex=stack[top--]; result[count]=inVex; count++; p=adjList[inVex].firstEdge; while(p){ outVex=p->adjvex; adjList[outVex].in--; if(adjList[outVex].in==0) stack[++top]=outVex; if(ve[inVex]+p->weight>ve[outVex]) ve[outVex]=ve[inVex]+p->weight; p=p->next; } } //判断拓扑排序是否正确 if(count==vertexNum) return true; return false; }