拓扑排序及应用


什么是拓扑排序:

对于一个有向图 G, 如果存在一种结点的序列,使得对于每条边 (u, v), 都有 u 在 v 的前面,则这个顺序叫做拓扑序,给图排拓扑序的过程即是拓扑排序

显然,只有 DAG 才存在拓扑序。

如何进行拓扑排序:

有两种方法:

1.dfs:

dfs 遍历 DAG, 并在遍历完后将结点放在当前序列的首部

—- 代码 —-(来自紫书)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int c[Mn];
int topo[Mn], t(n);
bool dfs
{
c[u] = -1 //访问标志
for(int v(0);v<n;++v)
{
if(G[u][v)
{
if(c[v]<0) return false; //存在有向环, 排序失败
else if(!c[v] && !dfs(v)) return false;
}
c[u] = 1; topo[--t]=u;
return true;
}

2.bfs:

运用一个队列,删除在队头的结点, 并寻找入度为 0 的点入队

—- 代码 —-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int topo[Mn];
int in[Mn]; //入度
int h(1),t(1);
for(int i(1);i<=n;++i)
if(!in[i]) topo[t++]=i;
while(h!=t)
{
for(edge* e(v[topo[h]]);e;e=e->next)
{
--in[e->e];
if(!in[e->e])
topo[t++] = e->e;
}
++h;
}

拓扑排序的作用:

首先,拓扑序可以用来定任务的起始时间,这也是一般书上讲的东西

其次,拓扑序可以判定一个有向图是不是 DAG

因为有且只有 DAG 才存在拓扑序

那么,如果将 DAG 的性质和定序结合起来会怎么样?

我们知道,DAG 与 dp 有密不可分的关系

而拓扑序可以给出 DAG 的处理顺序…

也就是说,拓扑序可以给出 DAG 上 dp 的计算顺序

这也是一般 DAG 上 dp 的优化思路