拓扑排序

拓扑排序是什么

oi wiki给出的拓扑排序定义如下：在一个 DAG(有向无环图)中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 $u$ 到 $v$ 的有向边 $(u, v)$ , 都可以有 $u$ 在 $v$ 的前面。

举个例子：

上图的拓扑排序可以是：

1 2 4 3 5 6 7
1 2 3 4 5 6 7
1 4 2 5 6 3 7

所以说，一个DAG的拓扑排序可能不止一种。

拓扑排序与DAG的关系

现在让我们不妨思考一下，为什么只有DAG才存在拓扑排序呢？

首先，对于无向图来说，从拓扑排序的定义来看，无向图不存在 $u$ 在 $\textit{v}$ 的前面这种逻辑关系，自然不存在拓扑排序；其次，对于有环的图来说，假设其存在拓扑排序，那么一定存在 $k, p$ 使得：

$a_{p+1}\rightarrow a_{p+2},a_{p+2}\rightarrow a_{p+3},a_{p+3}\rightarrow a_{p+4},...,a_{p+k-1}\rightarrow a_{p+k},a_{p+k}\rightarrow a_{p+1}$

根据拓扑排序的定义， $p+k < p+1$ ，而这显然是不可能的，所以也不存在拓扑排序

根据这个性质，拓扑排序还可以用于判断是否存在环，在下文中我们会详细介绍

拓扑排序的实现

了解完什么是拓扑排序后，接下来我们便可以去实现它了，这里介绍两种实现的方法

dfs

考虑到DAG本身有向，所以我们循着方向一直搜索的话一定能够得到一个拓扑序。那如果存在环呢？我们不妨思考一下，如何判断我们走的是环？这说明我们在本次dfs中，访问了一次正在访问的点，例如环 $A\rightarrow B\rightarrow C\rightarrow D\rightarrow A$ 中，我们正在访问 $A$ ，后面又访问了一次，这意味着我们绕了一圈，即这张图存在环。

所以，我们可以定义一个数组 $flag$ 来记录每个点的状态。

核心代码如下：

int flag[maxn]; //记录点的状态
vector<int> G[maxn]; //存图
vector<int> topo; //记录拓扑排序结果
int n; //点的数量

bool dfs(int u)
{
    flag[u] = -1; //表示正在访问这个点
    for(int i = 0; i < G[u].size(); i++) //遍历当前点的后继
    {
        int v = G[u][i];
        if(flag[v] == -1) //访问到了正在访问的点
            return false;
        else if(flag[v] == 0) //没被访问过
            if(!dfs(v)) //如果不存在拓扑序，逐层返回
                return false;
    }
    flag[u] = 1; //表示该点已被访问，且拓扑序存在
    topo.pushback(u); 记录答案
    return true;
}

bool toposort()
{
    topo.clear();
    memset(flag, 0, sizeof(flag));
    for(int i = 1; i <= n; i++)
        if(flag[i] == 0)
            if(!dfs(i)) //一旦存在环
                return false; //不存在拓扑序
    reverse(topo.begin(), topo.end());
    return true;
}

Kahn算法

也可以看作拓扑排序的bfs实现方法，其核心步骤如下：

初始将所有入度为0的点组成一个集合 $S$
从 $S$ 中取出一个点 $u$ ，压入拓扑序中，并遍历这个点的后继，将其与其后继的边删除，如果删除后其后继的入度为0，则将其压入 $S$ 中
重复执行以上操作

那么我们如何判断是否存在环呢？不难发现，对于一个环而言，其中任意一点的入度总是不为0，也就是说环上的所有点都不会被加入到集合 $S$ 中。所以，我们只需要在结束后判断拓扑序中点的数量是否为 $n$ 即可。

核心代码如下：

int to[maxn]; //记录每个点的入度
vector<int> G[maxn]; //存图
vector<int> topo; //记录排序结果
int n;

bool kahn()
{
    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(to[i] == 0) 
            q.push(i); //入度为0的点入队
    
    while(!q.empty())
    {
        int u = q.front();
        topo.push_back(u);
        q.pop();
        
        for(int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            to[v]--; //删除后继
            if(to[v] == 0) 
                q.push(v); //删除后入度为0， 入队
        }
	}
    
    if(topo.size() == n) //所有的点都被访问
        return true;
    return false;
}