友情支持

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

支付宝

微信

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

wx jikerizhi

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

Topological Sort (Graph) 拓扑排序

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

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

这种模式是这样奏效的：

  1. 初始化

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

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

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

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

  3. 找所有的起点

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

  4. 排序

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

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

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

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

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

    2. 重复上述过程，直到起点队列为空。

用一句话概括：将依赖关系转化成一张有向图，如果这张图中的节点没有循环依赖，那么则方案可行，否则方案不可行。

这里解释的是一种广度优先搜索，看 207. 课程表 - 官方题解，还存在一种深度优先搜索的处理办法，有机会尝试一下。

拓扑排序模式识别：

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

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

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

经典题目

  1. 207. 课程表

  2. 210. Course Schedule II

  3. [0269-alien-dictionary]

  4. [0444-sequence-reconstruction]

  5. [0310-minimum-height-trees]

参考资料

  1. 拓扑排序详解与实现

  2. 拓扑排序原理

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