文章目录拓扑排序是什么是拓扑排序？ 如何对拓扑排序？ 通过拓扑排序实现关键路径什么是关键路径？ 怎么寻求关键路径？ 实现关键路径寻求关键路径的示例过程
拓扑排序拓扑排序是什么？ 在图论中，3358www.Sina.com/是拓扑排序的所有顶点的线性序列(获得拓扑有序)。 此序列必须满足以下两个条件：
各顶点出现，只出现一次。 当有从顶点a到顶点b的路径时，系列中顶点a出现在顶点b的前面。 有一种说法认为，无环(DAG )具有拓扑排序，而非DAG图没有拓扑排序。
如何对拓扑排序？有向无环图
在有向图中选择没有前驱的顶点进行输出。 从图中删除此顶点及其尾的所有圆弧。 重复上述两个步骤，直到输出了所有顶点或上一个图中不再存在没有前驱的顶点。 后者的情况表明有向图中存在环。
图中，V1和V6只要没有前体，就可以选择其中一个。 假设先输出V6，则删除V6和弧V6、V4、V6、V5后，只有顶点V1没有前体，输出V1删除V1和弧V1、V2、V1、V3和V1、V4，然后V3和V4没有前体。 这样，您可以选择其中一个继续。 整个拓扑排序过程如上图所示。
在拓扑实现中，采用拓扑排序步骤：有向图的存储结构，并且在头节点中添加存储顶点入阶的数组。 进入度为零的顶点是没有前驱的顶点，删除顶点和以其为尾的弧的操作，可以通过用弧的顶点的进入度减去1的操作来实现。
statustopologicalsort(algraphg ) /有向图g采用邻表存储结构)/g如果没有循环，则输出g顶点的拓扑序列并返回OK，否则返回错误发现degree (g //对每个顶点输入深度in degree [0. vernum-1 ]输入堆栈(s )； for(I=0； iG.vexnum； 建造I//零入顶点堆栈S if！ indegree[I](/入)度为0者堆栈为push(s，I )； 计数=0； //将输出顶点计数为while (！ 堆栈深度(s ) ) {Pop(S )，I )； printf(I，G.vertices[i].data )； 出局； 输出//I号顶点并对for进行计数(p=g.vertices[I].firstarc； p； p=p-nextarc(k=p-adjvex； //I号顶点的每个邻接点的入(减去1 if )！ (--indegree[k] ) )/in )为0时，堆栈推送(s，k )； }if(countg.vexnum ) /该有向图中包含电路return ERROR； elsereturn OK； }对于具有n个顶点和e条弧的有向图，制作求出各顶点进入度的时间复杂度o(e )； 构建零入度顶点堆栈的时间复杂度为o(n )； 在拓扑排序过程中，如果有向图中没有循环，则每个顶点进入一次堆栈，一次从堆栈出来，减去1的操作在WHILE语句中执行总计e次，因此总计为邻接表。
如果有向图中没有循环，也可以利用深度优先遍历进行拓扑对齐。 由于图形中没有循环，从图形中的某一点进行深度优先搜索遍历时，DFS函数的顶点——出度为零的顶点首先退出，是拓扑顺序的最后一个顶点。 因此，脱离DFS函数的顺序记录的顶点序列是反向的拓扑顺序，如求出强连接成分时的finished排列中的顶点序列。
关键路径是什么？ 在代表时间复杂度为 O(n+e)项目的有向图中，顶点表示事件(例如V1 )，有向边表示活动(例如V1，V2=a1 )，边的权重值表示活动的持续时间。 这样的有向图被称为边所表示的活动的网。 在33558www.Sina.com/AOE网上，没有加边的顶点称为源点； 就像顶点V1一样。 在33558www.Sina.com/AOE网上，没有出现边缘的顶点称为终点； 就像顶点V9一样。AOE网：
只有在进入某个顶点的活动全部结束后，才会发生该顶点表示的事件； 例如，V5事件的发生需要a4和a5事件都结束。 只有在以某个顶点为代表的事件发生后，从该顶点出发的各项活动才开始； 例如，事件a7和a8只有在V5事件结束后才会启动。 在AOE网络中，必须完成所有活动才能到达目标，因此完成整个项目所需的时间(最短工期)必须是从源到目标的最大路径长度。 具有最大路径长度的路径称为源点：。 关键路径上的活动为终点：
设开始点为V1，则从V1到Vi的最长路径长度被称为事件Vi的AOE网的性质：。 这个时间是所有的
Vi 为尾的弧所表示的活动的最早开始时间。我们用 e(i) 表示活动 ai 的最早开始时间。还可以定义一个活动的最迟开始时间 l(i)，这是在不推迟整个过程完成的前提下，活动 ai 最迟必须开始进行的时间。两者之差 l(i)-e(i) 意味着完成活动 ai 的时间余量。我们把 l(i)=e(i) 的活动叫做关键活动。向关键路径要时间，向非关键路径要资源。
从前往后，计算工期与每项活动的最早开始时间；从后往前，倒推每项活动最晚开始时间。关键路径：最早开始时间=最晚开始时间
ve(j)：最早发生时间
vl(j)：最迟发生时间
根据上述算法，计算各顶点的 ve 值是在拓扑排序的过程中进行的，需对拓扑排序的算法作如下修改：
改写的拓扑排序代码：
Status TopologicalOrder(ALGraph G, Stack &T){//有向图G采用邻接表存储结构，求各顶点事件的最早发生时间 ve(全局变量) //T为拓扑序列顶点栈，S为零入度顶点栈 //若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则ERROR FindInDegree(G, indegree);//对各顶点求入度indegree[0..vernum-1] InitStack(S);//建零入度顶点栈S for(i=0;i<G.vexnum;i++)//建零入度顶点栈S if(!indegree[i])//入度为0者进栈 Push(S, i);InitStack(T);count = 0;ve[0..G.vexnum-1] = 0;//初始化 while(!StackEmpty(S)){Pop(S, j);Push(T, j);count++;//j号顶点入T栈并计数 for(p=G.vertices[j].firstarc; p; p=p->nextarc){k = p->adjvex;//对j号顶点的每个邻接点的入度减1 if(--indegree[k] == 0)//若入度减为0，则入栈 Push(S, k);if(ve[j]+ *(p->info)>ve[k])ve[k] = ve[j] + *(p->info);}}if(count < G.vexnum)//该有向图有回路 return ERROR;elsereturn OK;}关键路径算法：
Status CriticalPath(ALGraph G){//G为有向图，输出G的各项关键活动 if(!TopologicalOrder(G, T))return ERROR;vl[0..G.vexnum-1] = ve[G.vexnum-1];//初始化顶点事件的最迟发生事件 while(!StackEmpty(T)){//按拓扑逆序求各顶点的vl值 for(Pop(T, j),p=G.vertices[j].firstarc; p; p=p->nextarc){k = p->adjvex;dut = *(p->info);if(vl[k]-dut < vl[j])vl[j] = vl[k]-dut;}}for(j=0;j<G.vexnum;j++){//求ee，el和关键活动 for(p=G.vertices[j].firstarc; p; p=p->nextarc){k = p->adjvex;dut = *(p->info);ee = ve[j];el = vl[k]-dut;tag = (ee==el)?'*':'';printf(j, k, dut, ee, el, tag);//输出关键活动 }}} 上面两种算法的时间复杂度均为 O(n+e)，计算弧的活动最早开始时间和最迟开始时间的时间复杂度为 O(e)，所以总的求关键路径的时间复杂度为 O(n+e)。
上图的关键活动为 a1，a4，a7，a8，a10 和 a11。它们构成两条关键路径：(V1，V2，V5，V7，V9) 和 (V1，V2，V5，V8，V9)。
实践证明：用 AOE-网来估算某些工程完成的时间是非常有用的。只有在不改变网的关键路径的情况下，提高关键活动的速度才有效。若网中有几条关键路径，那么，单是提高一条关键路径上的关键活动的速度，还不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动速度。