拓扑排序

定义

拓扑排序（Topological sorting）要解决的问题是给一个有向图的所有节点排序。

这里直接使用OI-Wiki中举的例子来说明：

我们可以拿大学选课的例子来描述这个过程，比如学习大学课程中有：单变量微积分，线性代数，离散数学概述，概率论与统计学概述，语言基础，算法导论，机器学习。当我们想要学习 算法导论 的时候，就必须先学会 离散数学概述 和 概率论与统计学概述，不然在课堂就会听的一脸懵逼。当然还有一个更加前的课程 单变量微积分。

这些课程就相当于几个顶点$u$, 顶点之间的有向边$(u,v)$就相当于学习课程的顺序。显然拓扑排序不是那么的麻烦，不然你是如何选出合适的学习顺序。下面将介绍如何将这个过程抽象出来，用算法来实现。

但是如果某一天排课的老师打瞌睡了，说想要学习 算法导论，还得先学 机器学习，而 机器学习 的前置课程又是 算法导论，然后你就一万脸懵逼了，我到底应该先学哪一个？当然我们在这里不考虑什么同时学几个课程的情况。在这里，算法导论 和 机器学习 间就出现了一个环，显然你现在没办法弄清楚你需要学什么了，于是你也没办法进行拓扑排序了。因而如果有向图中存在环路，那么我们就没办法进行拓扑排序了。

因此我们可以说在一个[[DAG（有向无环图）]]中，我们将图中顶点以线性方式排序，使得对于任意顶点$u$到$v$的有向边$(u, v)$，都有$u$在$v$的前面。

或者说给定一个DAG，如果$i$到$j$有边，则认为$j$依赖于$i$，如果$i$到$j$有路径，则称$j$间接依赖于$i$； 拓扑排序的目标是将所有节点排序，使得在前面的节点不能依赖于排在后面的节点。

bfs

拓扑排序有广度优先搜索（bfs）和深度优先搜索（dfs）两种实现方式，这里我们先讨论bfs。

利用bfs实现拓扑排序需要根据节点的入度：

入度：有多少条边直接指向该节点

思路

1. 起始时，将所有入度为$0$的点放入队列q_in0；
2. 将队首元素出队，出队序列就是我们要求的拓扑序，对当前弹出的节点u，res.push_back(u)，遍历u的所有出度，即遍历所有由u直接指向的节点v，递减节点v的入度；
3. 如果节点v的入度变为0，将节点v入队；
4. 循环2、3流程直到队列为空；

如果res最后恰好有$n$个节点，说明原图为DAG，res中的节点序列即要求的拓扑序；否则说明图中存在环。

代码实现

vector<vector<int>> graph;
int n = graph.size();
int in[n]; // 存储每个节点的入度

bool toposrot() {
    vector<int> res;
    queue<int> q_in0;
    for (int i = 0; i < n; ++i) {
        if (in[i] == 0) {
            q_in0.push(i);
        }
    }
    while (!q_in0.empty()) {
        int u = q_in0.front();
        q_in0.pop();
        res.push_back(u);
        for (auto v : graph[u]) {
            if (--in[v] == 0) {
                q_in0.push(v);
            }
        }
    }
    if (res.size() == n) {
        for (auto i : res) {
            cout << i << " ";
        }
        return true;
    }
    return false;
}

dfs

todo