『拓扑排序』拓扑排序模板

2020-12-13 14:03

阅读：543

标签：while 查看 sort 计算 return 有向无环图 int 就是 void

拓扑排序学习前提须知

拓扑排序是对于一个图的所有节点进行排序，要求排序完后没有一个节点指向它前面的节点，那么这样我们就会得到一个拓扑排序后的数组，我们从后往前扫通过某种计算就能够得到从某一个点开始最多能到多少个点。

1、拓扑排序仅适用于有向无环图，当然也可以判定是否图为无环图

2、能够得到从一个点能到多少个其他的点，如果n在万以上，处理得当甚至能够过千万

拓扑排序需要满足一个很重要的条件就是，每次进入答案的点的入度一定为0，那么根据这个条件，我们就能得到我们的拓扑排序后的数组

void toposort() {
    std::queue q; //存储到目前为止入度为0的点
    std::vector ans; //储存答案
    for (int i = 1; i

『拓扑排序』拓扑排序模板

标签：while 查看 sort 计算 return 有向无环图 int 就是 void

原文地址：https://www.cnblogs.com/Nicoppa/p/11549836.html

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：『拓扑排序』拓扑排序模板
文章链接：http://soscw.com/essay/33659.html

亲，登录后才可以留言！