拓扑排序和关键路径是如何实现的

Question

如题所述

Answer 1

通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。注意：①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。②若图中存在有向环，则不可能使顶点满足拓扑次序。③一个DAG的拓扑序列通常表示某种方案切实可行。④一个DAG可能有多个拓扑序列。⑤当有向图中存在有向环时，拓扑序列不存在在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。关键路径用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网。AOE网常用于估算工程完成时间4、 求关键路径的算法(1) 输入e条弧<j,k>，建立AOE网的存储结构。(2) 从源点v1出发，令ve(1)=0,求 ve(j) 2<=j<=n。(3) 从汇点vn出发，令vl(n)=ve(n),求 vl(i) 1<=i<=n-1。(4) 根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。