# 7.17.拓扑排序

为了表明计算机科学家可以把任何东西变成一个图问题，让我们考虑做一批煎饼的问题。 菜谱真的很简单：1个鸡蛋，1杯煎饼粉，1汤匙油 和 3/4 杯牛奶。 要制作煎饼，你必须加热炉子，将所有的成分混合在一起，勺子搅拌。 当开始冒泡，你把它们翻过来，直到他们底部变金黄色。 在你吃煎饼之前，你会想要加热一些糖浆。 Figure 27将该过程示为图。

![7.17.拓扑排序.figure27](https://808160078-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lvj7ZGdGdwnWS_ALAOL%2F-Lvj7ZuTzf-cIehB0Acm%2F-Lvj7huu2SN3egDHv1XE%2F7.17.%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F.figure27.png?generation=1575970071025452\&alt=media) *Figure 27*

制作煎饼的困难是知道先做什么。从 Figure 27 可以看出，你可以从加热煎饼开始，或通过添加任何成分到煎饼。为了帮助我们决定应该做的每一个步骤的精确顺序，我们转向一个图算法称为 `拓扑排序`。

拓扑排序采用有向无环图，并且产生所有其顶点的线性排序，使得如果图 G 包含边（v，w），则顶点 v 在排序中位于顶点 w 之前。定向非循环图在许多应用中使用以指示事件的优先级。制作煎饼只是一个例子;其他示例包括软件项目计划，用于数据库查询的优先图以及乘法矩阵。

拓扑排序是深度优先搜索的简单但有用的改造。拓扑排序的算法如下：

1. 对于某些图 g 调用 dfs(g)。我们想要调用深度优先搜索的主要原因是计算每个顶点的完成时间。
2. 以完成时间的递减顺序将顶点存储在列表中。
3. 返回有序列表作为拓扑排序的结果。

Figure 28 展示了在 Figure 26 所示的薄煎饼制作图上由 dfs 构建的深度优先森林。 ![7.17.拓扑排序.figure28](https://808160078-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lvj7ZGdGdwnWS_ALAOL%2F-Lvj7ZuTzf-cIehB0Acm%2F-Lvj7huw1mzT6W--P0t5%2F7.17.%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F.figure28.png?generation=1575970070829483\&alt=media) *Figure 28*

最后，Figure 29 展示了将拓扑排序算法应用于我们的图形的结果。 现在所有的分支已被删除，我们知道确切的做煎饼的步骤顺序。

![7.17.拓扑排序.figure29](https://808160078-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lvj7ZGdGdwnWS_ALAOL%2F-Lvj7ZuTzf-cIehB0Acm%2F-Lvj7huyGjzXgKA5PffU%2F7.17.%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F.figure29.png?generation=1575970070946640\&alt=media) *Figure 29*
