7.17.拓扑排序 - Python 数据结构

返回介绍

7.17.拓扑排序

发布于 2019-08-07 字数 2015 浏览 844 评论 0

7.17.拓扑排序

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

7.17.拓扑排序.figure27

Figure 27

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

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

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

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

Figure 28 展示了在 Figure 26 所示的薄煎饼制作图上由 dfs 构建的深度优先森林。

7.17.拓扑排序.figure28

Figure 28

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

7.17.拓扑排序.figure29

Figure 29

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

目前还没有任何评论,快来抢沙发吧!