拓扑排序

简介

有向无环图:若一个有向图中不存在环,则称为有向无环图,简称DAG图(Directed Acyclic Graph)

AOV网(Activity On Vertex Network,用顶点表示活动的网):用DAG表示一个工程,顶点表示活动,有向边<Vi,Vj><V_i,V_j>表示活动ViV_i必须先于VjV_j进行。

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

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

实现

  1. 从AOV网中选择一个没有前驱(入度为0)的顶点并输出;
  2. 从网中删除该顶点和所有以它为起点的有向边;
  3. 重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止(说明有回路)。

逆拓扑序

  1. 从AOV网中选择一个没有后继(出度为0)的顶点并输出;
  2. 从网中删除该顶点和所有以它为终点的有向边;
  3. 重复1和2直到当前的AOV网为空。

思路

  1. 用一种容器(比如栈,队列,集合)维护当前所有入度为0的点。
  2. 每次从容器中取出一个点,删掉他和他的出边,这可能导致一些点入度为0,将新的入度为0的点加入容器。

代码

邻接表:时间复杂度 O(n+m)O(n+m), nn 表示点数,mm 表示边数

邻接矩阵:时间复杂度 O(n2)O(n^2)

也可以使用dfs实现

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int maxn = 1e5 + 5;
const int maxe = 2e5 + 5;

int n; // 点的数量
int h[maxn], e[maxe], ne[maxe], idx; // 邻接表存储所有边
int d[maxn];//每个点的入度
int print[maxn];//拓扑序列

//加边
void add(int x, int y) {
e[idx] = y; // 这样堆中会有很多冗余的点,但是在弹出的时候还是会弹出最小值2+x(x为之前确定的最短路径),并
ne[idx] = h[x]; // 标记st为true,所以下一次弹出3+x会continue不会向下执行。
h[x] = idx++;
d[y]++;//入度
}
//拓扑排序
bool topsort() {
stack<int> s;//存储入度为0的点

// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])//将所有入度为0的点入栈
s.push(i);

int cnt = 0;//记录当前已经输出的顶点数
while (!s.empty()) {//栈不空,存在入度为0的顶点
int t = s.top();
s.pop();
print[cnt++] = t;

for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (-- d[j] == 0)
s.push(j);
}
}

// 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
return cnt == n;
}

练习