【算法进阶】拓扑排序

· · 算法·理论

引子

假设你某天被你妈叫去做家务，给你了许多个任务，比如洗衣服、洗碗、做饭、扫地、拖地等等。你会发现有些任务之间有一些必然的顺序关系，晾衣服之前必须先洗衣服，拖地之前必须先扫地之类。如果我们把这些任务抽象为一个个点，它们之间的必然顺序视作点之间的有向边，那么我们就可以建出一个有向图了。

这时你想确定一下你做家务的顺序怎么办？这里我们引入一个新名词：拓扑排序。

概述

拓扑排序就是一种对一个有向图上的所有节点进行排序的方法。它并不复杂，甚至比较简单，毕竟你就算不把有向图建出来也能确定做家务的顺序，拓扑排序只是将这个过程抽象化罢了。

但还有一个问题，如果你妈某天喝多了，让你扫地之前必须拖地，拖地之前必须扫地，这时该怎么办？显然我们无法确定一个合理的顺序。如果按刚才的思路来想，那么这两件事就是有向图上的两个节点，而它们形成了一个 环。

无法确定顺序，也就意味着无法进行拓扑排序，因此拓扑排序只能在一个无环的有向图上进行，或者更清楚点，只能在一个 DAG 上进行。

说了这么多，终于要说到拓扑排序在 DAG 上的应用方式了。将一个有向图上的点按线性方式排序，并且使所有的子节点在这个排列中都排在其祖宗的后面，这就是拓扑排序的排序方式。

或者借用一下 OI wiki 上的定义：

给定一个 DAG，如果从 i 到 j 有边，则认为 j 依赖于 i。如果 i 到 j 有路径（i 可达 j），则称 j 间接依赖于 i。

拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。

求拓扑排序有两种算法，分别是 Kahn 算法和 DFS 算法。

Kahn 算法的本质是维护一个队列，队列内部存放当前所有入度为 0 的节点，然后将队列内部的数依次弹出，并删掉与其相关联的所有边（在代码里表现为子节点入度减一），如果子节点中出现了新的入读为 0 的节点，继续放入队列，重复以上过程，弹出所有节点的顺序即为一种拓扑序。

如果图中有 n 个节点，m 条边，则 Kahn 算法需要将所有点所有边都遍历一次，时间复杂度为 O(n+m)。

这里以拓扑排序板子题 P1347 排序 为例。以字母之间的关系建树，由于题目特殊性，每加入一条边就进行一次拓扑排序。如果说发现有环（还有节点没有入队），则矛盾，输出答案。而如果此时的图已经成链，则说明能够确定所有字母之间的顺序。如果直到结束都没有输出，则无法确定顺序。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=30;
int n,m,ind[N],ans[N];
vector <int > d[N];
int toposort ( int x )
{
    queue <int > q;
    int cnt=0,tot=0,t[N]; bool wy=1;
    for ( int i=0 ; i<n ; i++ )
    {
        t[i]=ind[i]; //因为要重复使用入度，多开一个数组
        if ( !t[i] ) q.push(i);
    }
    while ( !q.empty() )
    {
        if ( q.size()>1 ) wy=0; //有多个节点同时为根，无法成链
        int temp=q.front(); q.pop(); //不断弹出
        ans[++cnt]=temp; //记录可能的答案串
        for ( int i=0 ; i<d[temp].size() ; i++ )
            if ( --t[d[temp][i]]==0 ) q.push(d[temp][i]);
    }
    if ( cnt<n ) return 1; //有点未入队
    if ( wy ) return 2; //已经成链
    return 0; //都不符合
}
int main()
{
    scanf("%d %d",&n,&m);
    for ( int i=1 ; i<=m ; i++ )
    {
        char a,b; scanf("\n%c<%c",&a,&b);
        ind[int(b-'A')]++;
        d[int(a-'A')].push_back(int(b-'A')); //加一条新边
        int t=toposort(i);
        if ( a==b || t==1 ) //如果有环，直接退出
        {
            printf("Inconsistency found after %d ",i); puts("relations.");
            return 0;
        }
        if ( t==2 ) //如果成链，也退出
        {
            printf("Sorted sequence determined after %d relations: ",i);
            for ( int i=1 ; i<=n ; i++ ) printf("%c",ans[i]+'A'); puts(".");
            return 0;
        }
    }
    puts("Sorted sequence cannot be determined."); //前两种情况都不符合
    return 0;
}

如果要判断是否成链，则整个图中有且只有一个入度为 0 的节点。

如果要判断是否有环，则在拓扑排序之后遍历一遍，如果还有点的入度不为 0（没有入队过），则说明图中存在环。要证明也非常简单，如图：

可以看出，节点 4、5、6 构成了一个环，如果按照 Kahn 算法的方式入队，那么入队的顺序应该是 1、2、3 ，此时会发现 4 号节点无法入队，因为 6 号节点始终与其相关联，同理 5、6 号节点也无法入队，它们的入度始终大于 0。

另外，如果将 Kahn 算法中的队列替换为优先队列（大根堆/小根堆），则最终得到的拓扑序将会是字典序最大/最小的。在一些特殊的题目中，这一点将会很有用。此时时间复杂度为 O(n+m \log m)。

本蒟蒻不会，暂摆，着急想了解的自己去找。

我不会，长大后再学习

总结

拓扑排序是化图成链的一种好方法，并且其也能判断一个图中是否有环或成链。不过如果还想在一个有环的图上用拓扑排序的话，我们就需要用到缩点了，这是强连通分量的内容，想知道的可以看这里。