【图】拓扑排序

本文搬运自csdn

文章目录

• 拓扑排序
  • 什么是拓扑排序？
  • 怎么拓扑排序？
  • 拓扑排序实现
• 关键路径
  • 什么是关键路径？
  • 怎么求关键路径？
  • 关键路径实现
  • 求关键路径过程示例

拓扑排序

什么是拓扑排序？

  在图论中，拓扑排序是一个有向无环图的所有顶点的线性序列(获得拓扑有序序列)。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

怎么拓扑排序？

拓扑排序步骤：

1. 在有向图中选一个没有前驱的顶点且输出之。
2. 从图中删除该顶点和所有以它为尾的弧。

  重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。

  图中，V1 和 V6 没有前驱，则可任选一个。假设先输出 V6，在删除 V6 及弧 <V6, V4>,<V6, V5> 之后，只有顶点 V1 没有前驱，输出 V1 且删去 V1 及弧 <V1, V2>,<V1, V3> 和 <V1, V4>，之后 V3 和 V4 都没有前驱。依此类推，可从中任选一个继续进行。整个拓扑排序的过程如上图。

拓扑排序实现

  我们采用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组。入度为零的顶点即为没有前驱的顶点，删除顶点以及它为尾的弧的操作，则可换以弧头顶点的入度减 1 来实现。

Status TopologicalSort(ALGraph G){
	//有向图G采用邻接表存储结构 
	//若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR 
	FindInDegree(G, indegree);//对各顶点求入度indegree[0..vernum-1] 
	InitStack(S);
	for(i=0;i<G.vexnum;i++)//建零入度顶点栈S 
		if(!indegree[i])//入度为0者进栈 
			Push(S, i);
	count = 0;//对输出顶点计数 
	while(!StackEmpty(S)){
		Pop(S, i);	printf(i, G.vertices[i].data);	count++;//输出i号顶点并计数 
		for(p=G.vertices[i].firstarc; p; p=p->nextarc){
			k = p->adjvex;//对i号顶点的每个邻接点的入度减1 
			if(!(--indegree[k]))//若入度减为0，则入栈 
				Push(S, k);
		}
	}
	if(count<G.vexnum)//该有向图有回路 
		return ERROR;
	else
		return OK;
}

  对有 n 个顶点和 e 条弧的有向图而言，建立求各顶点的入度的时间复杂度 O(e)；建零入度顶点栈的时间复杂度为 O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减 1 的操作在 WHILE 语句中总共执行 e 次，所以，总的**时间复杂度为 O(n+e)**。
  当有向图中无环时，也可利用深度优先遍历进行拓扑排序，因为图中无环，则由图中某点出发进行深度优先搜索遍历时，最先退出 DFS 函数的顶点即出度为零的顶点，是拓扑有序序列中最后一个顶点。由此，按退出 DFS 函数的先后记录下来的顶点序列(如同求强连通分量时 finished 数组中的顶点序列)即为逆向的拓扑有序序列。

关键路径

什么是关键路径？

AOE网： 在一个表示工程的带权有向图中，用顶点表示事件（如V1），用有向边表示活动（如<V1,V2> = a1），边上的权值表示活动的持续时间，称这样的有向图为边表示的活动的网。
源点： 在AOE网中，没有入边的顶点称为源点；如顶点V1。
终点： 在AOE网中，没有出边的顶点称为终点；如顶点V9。
AOE网的性质：

1. 只有在进入某顶点的活动都已经结束，该顶点所代表的事件才发生；例如，V5 事件发生需要 a4 和 a5 两个活动都结束。
2. 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才开始；例如，V5 事件结束，活动 a7 和 a8 活动才能开始。
   

  在AOE网中，所有活动都完成才能到达终点，因此完成整个工程所必须花费的时间（即最短工期）应该为源点到终点的最大路径长度。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动。
  假设开始点是 V1，从 V1 到 Vi 的最长路径长度叫做事件 Vi 的最早发生事件。这个时间决定了所有以 Vi 为尾的弧所表示的活动的最早开始时间。我们用 e(i) 表示活动 ai 的最早开始时间。还可以定义一个活动的最迟开始时间 l(i)，这是在不推迟整个过程完成的前提下，活动 ai 最迟必须开始进行的时间。两者之差 l(i)-e(i) 意味着完成活动 ai 的时间余量。我们把 l(i)=e(i) 的活动叫做关键活动。

向关键路径要时间，向非关键路径要资源。

1. 从前往后，计算工期与每项活动的最早开始时间；
2. 从后往前，倒推每项活动最晚开始时间。
3. 关键路径：最早开始时间=最晚开始时间

怎么求关键路径？

ve(j)：最早发生时间
vl(j)：最迟发生时间

1. 输入 e 条弧<j, k>，建立 AOE-网的存储结构；
2. 从源点 v0 出发，令 ve[0]=0，按拓扑有序求其余各顶点的最早发现时间 ve[i] (1≤i≤n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数 n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤(3)。
3. 从汇点 vn 出发，令 vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i] (n-2≥i≥2)；
4. 根据各顶点的 ve 和 vl 值，求每条弧 s 的最早开始时间 e(s) 和最迟开始时间 l(s)。若某条弧满足条件 e(s)=l(s)，则为关键活动。

  根据上述算法，计算各顶点的 ve 值是在拓扑排序的过程中进行的，需对拓扑排序的算法作如下修改：

1. 在拓扑排序之前设初值，令 ve[i]=0 (0≤i≤n-1)；
2. 在算法中增加一个计算 vj 的直接后继 vk 的最早发生时间的操作：若 ve[j]+dut(<j, k>) > ve[k]，则 ve[k]=ve[j]+dut(<j, k>)；
3. 为了能按逆拓扑有序序列的顺序计算各顶点的 vl 值，需记下在拓扑排序的过程中求得的拓扑有序序列，这需要在拓扑排序算法中，增设一个栈以记录拓扑有序序列，则在计算求得各顶点的 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;
	else
		return 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-网来估算某些工程完成的时间是非常有用的。只有在不改变网的关键路径的情况下，提高关键活动的速度才有效。若网中有几条关键路径，那么，单是提高一条关键路径上的关键活动的速度，还不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动速度。

版权声明：本文为CSDN博主「qw&jy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43448856/article/details/119959241