Day 19：深度优先搜寻(DFS)与拓朴排序(topological sorting)

深度优先搜寻(depth-first search, DFS)是一种搜寻整张图所有节点的演算法。它的名称也表达出跟广度优先搜寻的顺序不太一样，它是从根节点(树的情况)，或任意节点(图的情况)开始，尽可能搜寻所有可以抵达的子节点，直到分支的尽头、没有子节点的地方，再回溯进行同样的搜寻。

以下图为例，节点上的数字即为深度优先搜寻的顺序。从根节点1开始，检查其中一个尚未检查的子节点2，并持续检查子节点的子节点，直到没有子节点的4为止再回头。回溯的方法是回到上一个有子节点的分支，例如4回溯到3，并检查3的另一个子节点5。

虽然一样是搜寻所有的节点，但这样的顺序让深度优先搜寻可以应用在不同地方，其中一个就是拓朴排序(topological sorting)。

拓朴排序是指将一个有向图的节点排序，方式是如果两节点之间边的方向是u到v，则在排序中节点u会在节点v前面。

例如说下图中节点7和8的方向是7到8，所以在拓朴排序中7一定出现在8前面。一张图不一定只有一种拓朴排序，例如这张图的一种排序可以是5, 7, 3, 11, 8, 2, 9, 10，也可以是3, 7, 8, 5, 11, 9, 10, 2。

如果直接对这张图进行深度优先搜寻，并依搜寻顺序将节点加入阵列中，并不会得到拓朴排序的结果(例如从5开始深度优先搜寻的话11会在7前面，但拓朴排序7应该在11前面)。但我们可以稍微改变方式，来进行拓朴排序。

方法是：从任一节点开始，用递回的方式进行深度优先搜寻，直到没有子节点或到达已经搜寻过的节点，再将搜寻过节点加到堆叠中。

例如从8开始深度优先搜寻，到子节点9後没有子节点，所以将节点加入堆叠中
stack = [9, 8]

接着从5开始深度优先搜寻，搜寻的节点为5, 11, 2, 10 (9已经搜寻过)，将节点加入堆叠中
stack = [9, 8, 10, 2, 11, 5]

接着搜寻7，子节点都已搜寻过，将7加入堆叠中
stack = [9, 8, 10, 2, 11, 5, 7]

最後搜寻3，子节点都已搜寻过，将3加入堆叠中
stack = [9, 8, 10, 2, 11, 5, 7, 3]

过程中搜寻到分支的终点才将节点加入堆叠，而非每搜寻一个就加入一次，这样确保每条分支的节点顺序。最後因为堆叠後进先出的原则，输出後可以得到拓朴排序的数列[3, 7, 5, 11, 2, 10, 8, 9]。

那麽，拓朴排序可以用在什麽情境呢？我们可以把节点的有向边想成表达事情之间的先後关系。例如有向边ab，可以代表a任务有优先性，或必须先完成a任务才能完成b任务，而拓朴排序既是以边的方向排序，自然就可以用来代表任务顺序。

实际例子就好比大学会对某些课程有挡修的规定。例如学生必须上完化学1才能上化学2，另外必须修完微积分1才能修微积分2，但化学1和微积分1之间就没有顺序的限制。若课程之间有类似这样关系，则所有课程的拓朴排序就是一个可行的修课顺序。