Topological Sorting
2021-05-06
0. 前言
所有的问题都可以被转换为 Graph problem，比如下面这个例子：
- 假如我们要做一些煎饼，每个煎饼需要 1 个蛋、一杯糊糊，一汤匙油，四分之三杯牛奶。
- 我们做煎饼必须要把锅子加热，把所有的材料都倒进去搅拌。
- 当煎饼开始冒泡的时候你就翻面，直到底部变成金黄色。
- 吃煎饼之前要加热一些枫糖浆。
这个过程可以被抽象成下面这幅图，最难的点在于第一步到底应该做什么，你可以先去热锅子，也可以准备材料。
不过呢，程序员们可以用一个 graph algorithm —— topological sort 来帮助我们做出一个流程图。
1. 何为 Topology
Topology 的中文翻译是拓扑，不得不说这两个字太抽象了。。完全搞不懂它是啥。
找了个CSDN的翻译：
所谓“拓扑”就是把实体抽象成与其大小、形状无关的“点”，而把连接实体的线路抽象成“线”，进而以图的形式来表示这些点与线之间关系的方法，其目的在于研究这些点、线之间的相连关系。
表示点和线之间关系的图被称为拓扑结构图。
拓扑结构与几何结构属于两个不同的数学概念。在几何结构中，我们要考察的是点、线之间的位置关系，或者说几何结构强调的是点与线所构成的形状及大小。如梯形、正方形、平行四边形及圆都属于不同的几何结构，但从拓扑结构的角度去看，由于点、线间的连接关系相同，从而具有相同的拓扑结构即环型结构。也就是说，不同的几何结构可能具有相同的拓扑结构。
大致意思就是把 node 和 edge 抽象成一个图，然后研究点和线之间的关系。
所以可以近似认为跟我们学的 Graph 原来就是一个东西？？只不过换了个高大上的名词，Topological sort 是不是就等于 graph sort 呢？？
我暂且这么认为吧~
2. Topological Sorting
这个排序算法的 input 是有方向的，首尾不相连（也就是没有大循环）的一个 graph，名为 Directed acyclic graph；
它的 output 是一个线性的、包含所有 node 的，以及前后 node 之间是有 edge 相连的一个 list。
A topological sort takes a directed acyclic graph and produces a linear ordering of all its vertices such that if the graph 𝐺G contains an edge (𝑣,𝑤) then the vertex 𝑣 comes before the vertex 𝑤 in the ordering.
Directed acyclic graph
这种图常用于表示流程，比如我们举的那个例子：做煎饼。
它还可以用于项目管理、优化数据库query等。
Directed acyclic graphs are used in many applications to indicate the precedence of events. Other examples include software project schedules, precedence charts for optimizing database queries, and multiplying matrices.
Topological Sorting
它其实是 DFS 的一个变体，逻辑如下：
- 调用 dfs function，计算 finish time；
- 把所有 node 根据 finish time 从大到小排序，存入一个 list；
- 返回这个排序后的 list ，作为 Topological Sorting 的结果。
举例
第一步：计算 finish time
第二步：排序
