友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

Topological Sort (Graph) 拓扑排序

拓扑排序模式用来寻找一种线性的顺序，这些元素之间具有依懒性。比如，如果事件B依赖于事件A，那A在拓扑排序顺序中排在B的前面。

这种模式定义了一种简单方式来理解拓扑排序这种技术。

这种模式是这样奏效的：

  1. 初始化

    1. 借助于HashMap将图保存成邻接表形式。

    2. 找到所有的起点，用HashMap来帮助记录每个节点的入度

  2. 创建图，找到每个节点的入度

    1. 利用输入，把图建好，然后遍历一下图，将入度信息记录在HashMap中

  3. 找所有的起点

    1. 所有入度为0的节点，都是有效的起点，而且我们讲他们都加入到一个队列中

  4. 排序

    1. 对每个起点，执行以下步骤

      1. 把它加到结果的顺序中

      2. 将其在图中的孩子节点取到

      3. 将其孩子的入度减少1

      4. 如果孩子的入度变为0，则改孩子节点成为起点，将其加入队列中

    2. 重复（a）过程，直到起点队列为空。

拓扑排序模式识别：

  • 待解决的问题需要处理无环图

  • 你需要以一种有序的秩序更新输入元素

  • 需要处理的输入遵循某种特定的顺序

经典题目

  1. 207. Course Schedule

  2. 210. Course Schedule II

  3. [0269-alien-dictionary]

  4. [0444-sequence-reconstruction]

  5. [0310-minimum-height-trees]

Topological Sort (medium)

All Tasks Scheduling Orders (hard)

参考资料

  1. 拓扑排序详解与实现

  2. 拓扑排序原理

← Previous: Union Find Set 查并集 | ↑ Up: LeetCode 解题笔记 | Next: Brute Force 暴力破解 →