- ChungZH's blog
拓扑排序笔记
- 2022-8-26 17:17:01 @
欢迎访问我的博客:blog.chungzh.cn
引入
给定一张有向无环图(DAG, Directed Acyclic Graph),对其顶点进行排序,使得对于每条从 到 的有向边 , 在排序中都在 的前面。这种排序就称为拓扑排序(Topological sorting)。
当且仅当图中没有定向环时(即有向无环图),才有可能进行拓扑排序。如果排序失败,就说明该有向图存在环,不是 DAG。
任何有向无环图至少有一个拓扑排序。
举例:在某校的选课系统中,存在这样的规则:每门课可能有若干门先修课,如果要修读某一门课,则必须要先修读此课程所要求的先修课后才能修读。假设一个学生同时只能修读一门课程,那么,被选课系统允许的他修完他需要所有课程的顺序是一个拓扑序。
在这个例子中,每一门课程对应有向图中的一个顶点,每一个先修关系对应一条有向边(从先修课指向需要先修课的课)。
算法
Kahn 算法
初始状态下,集合 装着所有入度为 的点, 是一个空列表。
每次从 中任意取出一个点 放入 , 然后将 的所有边 删除。对于边 ,若将该边删除后点 的入度变为 ,则将 放入 中。
不断重复以上过程,直到集合 为空。检查图中是否存在任何边,如果有,那么这个图一定有环路,否则返回 , 中顶点的顺序就是拓扑排序的结果。
基本上就是 BFS 的框架。
代码实现:
int n, m;
vector<int> G[MAXN];
int in[MAXN]; // 存储每个结点的入度
bool toposort() {
vector<int> L;
queue<int> S;
for (int i = 1; i <= n; i++)
if (in[i] == 0) S.push(i);
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) {
for (auto i : L) cout << i << ' ';
return true;
} else {
return false;
}
}
DFS 算法
借助 DFS 完成拓扑排序:在访问完一个结点之后把它加到当前拓扑序的首部。
代码实现:
当 c[u] == 0
时,表示从来没有被访问过(从来没有调用过 dfs(u)
);c[u] == 1
时,表示已经访问过,而且还递归访问过它的所有子孙(即调用过 dfs(u)
且已返回);c[u] == -1
时表示正在访问(即递归调用 dfs(u)
正在栈帧中,尚未返回)。
int n, m;
vector<int> G[MAXN];
int c[MAXN], topo[MAXN], t;
bool dfs(int u) {
c[u] = -1;
for (auto v : G[u]) {
if (c[v] < 0)
return false;
else if (c[v] == 0 && !dfs(v))
return false;
}
c[u] = 1;
topo[--t] = u;
return true;
}
bool toposort() {
t = n;
memset(c, 0, sizeof(c));
for (int i = 1; i <= n; i++)
if (!c[i])
if (!dfs(i)) return false;
return true;
}
练习
参考资料
- OI Wiki CC BY-SA 4.0
- 《算法竞赛入门经典》