主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
拓扑排序
最后更新于 2025-08-28 16:28:40
作者
yyycj
分类
算法·理论
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
拓扑排序，是 Toposort 的音译。 对于一个有向无环图，如果顶点 $u$ 能到达顶点 $v$，那么在序列中 $u$ 在 $v$ 的前面，最后由 $n$ 个顶点形成的任意一种（因为可能由多个序列均满足情况）序列叫做拓扑序列，求拓扑序列的过程叫拓扑排序。 由于只有有向无环图才有拓扑序列，所以有向无环图也叫做拓扑图。 由于顶点 $u$ 能到达顶点 $v$，那么在序列中 $u$ 在 $v$ 的前面，所以入度为 $0$ 的顶点已经处于序列的最前面，接下来就是 bfs 的过程了，每次从队列顶取出顶点时存放进一个序列里，接着让这个顶点能到达的点的入度都减 $1$，如果某个点的入度为 $0$，就让它加入队列，最后就能得到一种拓扑序列。 代码： ```cpp int head = 1, tail = 0; for (int i = 1; i <= n; i++) { if (d[i] == 0) q[++tail] = i; } while (head <= tail) { int u = q[head++]; for (int i : edge[u]) { if (--d[i] == 0) q[++tail] = i; } } ```
正在渲染内容...
点赞
0
收藏
0
