拓扑排序的C++实现

tags: C++ DSA Sort GT

写在前面

写一下有向无环图(DAG, Directed Acyclic Graph)上的拓扑排序, 废话不多说了, 介绍部分大家可以参考算法导论或者 oi-wiki.

https://oi-wiki.org/graph/topo/;

我写的完整代码:
Topological-Sort

我们可以拿大学选课的例子来描述这个过程，比如学习大学课程中有：单变量微积分，线性代数，离散数学概述，概率论与统计学概述，语言基础，算法导论，机器学习。当我们想要学习 算法导论 的时候，就必须先学会 离散数学概述 和 概率论与统计学概述，不然在课堂就会听的一脸懵逼。当然还有一个更加前的课程 单变量微积分。这些课程就相当于几个顶点 , 顶点之间的有向边 就相当于学习课程的顺序。显然拓扑排序不是那么的麻烦，不然你是如何选出合适的学习顺序。下面将介绍如何将这个过程抽象出来，用算法来实现。

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

思路

有两种实现方法, 一种是基于 BFS 的, 叫做 Kahn 算法, 本质上就是广度优先搜索, 统计入度为 0 的所有节点, 放入结果集合, 同时将入度为 1 的放入结果集合, 最后判断结果集大小是不是结点个数(这样才说明图上每一个节点都遍历到了, 也即图是 DAG).

还有一种是基于深度优先搜索的, 在 DFS 的时候, 遍历直到节点没有出度(即到达函数结尾, return 之前), 此时的节点就是"末尾"节点, 也就是说一条深搜路径的结尾, 这时候放入栈中, 结果集就是栈的出栈序列.

实现: BFS

bool topoSort_Kahn() {
    vector<int> L;
    queue<int> S;
    // 计算节点入度
    for (auto v : G)
        for (int i : v) ++in[i];
    // 存入度为 0 的节点
    for (int i{}; i < n; ++i)
        if (in[i] == 0) S.push(i); 
    // BFS
    while (!S.empty()) {
        int u = S.front();
        S.pop();
        L.push_back(u);
        for (auto v : G[u]) {
            if (--in[v] == 0) S.push(v);
        }
    }
    if (L.size() == n) {
        cout << "排序结果:\n" << L;
        return true;
    }
    return false;
}

实现: DFS

void topoSort_DFS() {
    //
    bool visited[n];
    memset(visited, false, sizeof(visited));
    stack<int> st;

    function<void(int)> dfs = [&](int v) {
        visited[v] = true;
        for (auto i : G[v])
            if (!visited[i]) dfs(i);
        st.emplace(v);
    };
    for (int i{}; i < n; ++i)
        if (!visited[i]) dfs(i);
    cout << st;
}

代码示例

utility-function

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;


ostream& operator<<(ostream& os, const vector<int>& v) {
    for (auto i : v) os << i << " ";
    return os << endl;
}
ostream& operator<<(ostream& os, queue<int> v) { // pass by value
    for (; !v.empty(); v.pop()) os << v.front() << " ";
    return os << endl;
}
ostream& operator<<(ostream& os, stack<int> v) { // pass by value
    for (; !v.empty(); v.pop()) os << v.top() << " ";
    return os << endl;
}

针对上面这个图, 采用不同的拓扑排序策略, 得到的排序结果不同:

// 图的例子: 参见
// https://oi-wiki.org/graph/images/topo-example.svg
// 邻接表
vector<vector<int>> G{
    {1, 5, 6}, {},  {0, 3},       {5}, {},   {4}, {4, 9},
    {6},       {7}, {10, 11, 12}, {},  {12}, {},
};

int n = G.size(); // n: vertex
// int m{15};        // m: edge
// 存储结点的入度
vector<int> in(n);
// 1, 1, 0, 1, 2, 2, 2, 1, 0, 1, 1, 1, 2

int main() {
    // topoSort_Kahn(); // BFS
    // 2 8 0 3 7 1 5 6 4 9 10 11 12
    topoSort_DFS();
    // 8 7 2 3 0 6 9 11 12 10 5 4 1
}