算法理论——拓扑排序（一定要会）

文章目录
解释证明例题题目描述示例拓扑排序解法

解释
为了方便，我们令点数为n ，边数为m 。
在图论中，一个有向无环图必然存在至少一个拓扑序与之对应，反之亦然。
拓扑排序：简单来说，就是将图中的所有节点展开成一维序列，对于序列中任意的节点 ，如果在序列中 在 的前面，则说明在图中存在从 出发达到 的通路，即 排在 的前面。反之亦然。
同时，我们需要知晓「入度」和「出度」的概念：
入度：有多少条边直接指向该节点；出度：由该节点指出边的有多少条。
因此，对于有向图的拓扑排序，我们可以使用如下思路输出拓扑序（BFS 方式）：
起始时，将所有入度为 的节点进行入队（入度为 ，说明没有边指向这些节点，将它们放到拓扑排序的首部，不会违反拓扑序定义）；从队列中进行节点出队操作，出队序列就是对应我们输出的拓扑序。对于当前弹出的节点 x，遍历x 的所有出度y，即遍历所有由 x直接指向的节点y，对y

算法理论——拓扑排序（一定要会）最先出现在Python成神之路。