写在前面
写一下有向无环图(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
}