拓扑排序及应用

发表于 | 分类于 ， ，

什么是拓扑排序:

对于一个有向图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的优化思路