Python 中的拓扑排序

在本教程中，我们将学习深度优先搜索的一个重要应用。我们将理解拓扑排序的概念、它的工作原理以及如何使用 Python 编程语言实现它。最后，我们将学习算法的时间复杂度以及拓扑排序的应用。让我们来介绍一下拓扑排序。

什么是拓扑排序？

拓扑排序是图论中的一个重要应用，用于解决许多现实生活中的问题。它是一种算法，接收一个有向无环图，并返回节点的序列。每个节点都会出现在指向它的其他节点之前。有向无环图是一种图，它在一个节点到另一个节点之间具有有向边，而不会产生任何环。请记住，如果图不是有向无环图，拓扑排序将不起作用。数组中的节点顺序称为拓扑顺序。

假设我们有一组任务，每个任务都依赖于其他任务。我们想以这样一种方式安排这些任务，以确保依赖关系不会被违反。在任务链中后面的任何任务，只有在它前面的所有任务都完成后才能执行。

图的拓扑排序有助于我们维持这种排序。

每个图可能有一个以上的拓扑排序。这取决于图中节点的入度。该算法从入度为 0 的节点（没有传入边）开始。

算法

以下是拓扑排序算法。

1. 第一步是识别没有入度（没有传入边）的节点，并将其选为图的源节点。
2. 现在删除入度为零的源节点及其相关的边。删除的顶点将被添加到结果数组中。
3. 删除出边后，更新相邻节点的入度。
4. 上述步骤将重复进行，直到图为空。

我们在过程结束时获得的结果数组称为有向图的拓扑顺序。如果还有一些节点剩下但它们有传入边，这意味着图不是无环的。如果给定的图不是无环的，则不存在拓扑排序。

Python 拓扑排序代码

输出

The Topological Sort Of The Graph Is:  
[0, 1, 2, 3, 4]

拓扑排序时间复杂度

拓扑排序的时间复杂度为 O(M +N)，其中 M 是图中的边数，N 是图中的节点数。

应用

拓扑排序提供了许多现实生活中的解决方案——

• 它用于课程安排问题中来安排作业。
• 它用于依赖性解析。
• 它在非常少的努力下找到句子顺序非常有益。
• 它有助于识别图中是否存在环。
• 在 Excel 或电子表格中重新计算公式值时，它用于对单元格求值进行排序。
• 拓扑排序有助于找到操作系统中的死锁条件。

结论

本教程包含了拓扑排序算法的概念及其实现。拓扑排序在现实生活应用中具有自身的重要性。在探索和处理树和图时，它起着至关重要的作用。拓扑排序使过程更简单高效，因此强烈建议清楚地理解它。