【图】拓扑排序
慕雪年华

本文搬运自csdn

文章目录

拓扑排序

什么是拓扑排序?

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

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

有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。

image

怎么拓扑排序?

拓扑排序步骤:

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

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

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

拓扑排序实现

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 活动才能开始。
    image

  在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 值之后,从栈顶至栈底便为逆拓扑有序序列。

关键路径实现

改写的拓扑排序代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
}

关键路径算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)**。

求关键路径过程示例

image
image

上图的关键活动为 a1,a4,a7,a8,a10 和 a11。它们构成两条关键路径:(V1,V2,V5,V7,V9) 和 (V1,V2,V5,V8,V9)。

实践证明:用 AOE-网来估算某些工程完成的时间是非常有用的。只有在不改变网的关键路径的情况下,提高关键活动的速度才有效。若网中有几条关键路径,那么,单是提高一条关键路径上的关键活动的速度,还不能导致整个工程缩短工期,而必须提高同时在几条关键路径上的活动速度。

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