拓扑排序算法： Python, C++ 例如：
陈莎拉
什么是拓扑排序算法？
拓扑排序又称为 Kahn 算法，是一种流行的排序算法。拓扑排序使用有向图作为输入，对节点进行排序，使每个节点都出现在其指向的节点之前。
该算法应用于有向无环图 (DAG)，使得每个节点在排序数组中出现在其指向的所有其他节点之前。该算法会重复执行某些规则，直到排序完成。
为了简化，请看以下示例：
有向图
这里我们可以看到，“A”没有入度。入度是指指向某个节点的边的度数。“B”和“C”依赖于“A”，那么“E”又依赖于“D”和“F”节点。有些节点依赖于其他节点。
以下是上述图表的另一种表示方法：
每个节点的依赖关系（线性排序）
因此，当我们将 DAG（有向无环图）传递给拓扑排序时，它将为我们提供一个具有线性排序的数组，其中第一个元素没有依赖性。
这是执行此操作的步骤：
步骤1） 查找具有零个传入边的节点，即具有零度的节点。
步骤2） 将入度为零的节点存储在队列或栈中，并从图中移除该节点。
步骤3） 然后删除该节点的出边。这将减少下一个节点的入度数。
拓扑排序要求图数据结构中不能包含任何环。如果一个图满足以下要求，则可将其视为有向无环图（DAG）：
- 一个或多个入度值为零的节点。
- 该图不包含任何环。
只要图中存在节点且该图仍为有向无环图（DAG），我们就会执行上述三个步骤。否则，算法将陷入循环依赖，Kahn 算法将无法找到入度为零的节点。
拓扑排序的工作原理
这里，我们将使用“卡恩算法”进行拓扑排序。假设我们有如下图：
以下是卡恩算法的步骤：
步骤1） 计算图中所有节点的入度或入边。
注意：
- 入度表示指向该节点的有向边。
- 出度表示来自某个节点的有向边。
以下是上述图表的入度和出度：
步骤2） 找到入度为零或入边数为零的节点。入度为零的节点意味着没有边指向该节点。节点“A”的入度为零，这意味着没有边指向节点“A”。因此，我们将执行以下操作：
- 删除此节点及其出度边（向外的边）。
- 将节点放入队列中以便排序。
- 更新“A”的邻居节点的入度数。
步骤3） 我们需要找到一个入度为零的节点。在这个例子中，“B”和“C”的入度均为零。我们可以选择其中任何一个。我们选择“B”并将其从图中删除。然后更新其他节点的入度值。完成这些操作后，我们的图和队列将如下所示：
步骤4） 节点“C”没有入边。因此，我们将节点“C”从图中移除并放入队列。我们还可以删除从“C”出发的出边。现在，我们的图将如下所示：
步骤5） 我们可以看到节点“D”和“F”的入度均为零。我们将取出一个节点并将其放入队列中。首先取出节点“D”。那么节点“E”的入度将变为1。现在，从D到E之间没有节点。我们需要对节点“F”执行相同的操作，结果如下：
步骤6） 节点“E”的入度（入边数）和出度（出边数）都变为零。因此，我们满足了节点“E”的所有前提条件。现在，我们将“E”放在队列末尾。至此，队列中已无剩余节点，算法结束。
昵称 Code 用于拓扑排序
以下是使用 Kahn 算法进行拓扑排序的伪代码。
function TopologicalSort( Graph G ): for each node in G: calculate the indegree start = Node with 0 indegree G.remove(start) topological_list = [start] while node with 0 indegree present: topological_list.append(node) G.remove(node) // Update indegree of present nodes return topological_list
拓扑排序也可以使用 DFS 来实现（深度优先搜索) 方法。但是，该方法是递归方法。Kahn 算法比 DFS 方法更有效。
C++ 拓扑排序的实现
#include<bits/stdc++.h> using namespace std; class graph{ int vertices; list<int> *adjecentList; public: graph(int vertices){ this->vertices = vertices; adjecentList = new list<int>[vertices]; } void createEdge(int u, int v){ adjecentList[u].push_back(v); } void TopologicalSort(){ // filling the vector with zero initially vector<int> indegree_count(vertices,0); for(int i=0;i<vertices;i++){ list<int>::iterator itr; for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){ indegree_count[*itr]++; } } queue<int> Q; for(int i=0; i<vertices;i++){ if(indegree_count[i]==0){ Q.push(i); } } int visited_node = 0; vector<int> order; while(!Q.empty()){ int u = Q.front(); Q.pop(); order.push_back(u); list<int>::iterator itr; for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){ if(--indegree_count[*itr]==0){ Q.push(*itr); } } visited_node++; } if(visited_node!=vertices){ cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl; return; } for(int i=0; i<order.size();i++){ cout<<order[i]<<"\t"; } } }; int main(){ graph G(6); G.createEdge(0,1); G.createEdge(0,2); G.createEdge(1,3); G.createEdge(1,5); G.createEdge(2,3); G.createEdge(2,5); G.createEdge(3,4); G.createEdge(5,4); G.TopologicalSort(); }
输出
0 1 2 3 5 4
Python 拓扑排序的实现
from collections import defaultdict class graph: def __init__(self, vertices): self.adjacencyList = defaultdict(list) self.Vertices = vertices # No. of vertices # function to add an edge to adjacencyList def createEdge(self, u, v): self.adjacencyList[u].append(v) # The function to do Topological Sort. def topologicalSort(self): total_indegree = [0]*(self.Vertices) for i in self.adjacencyList: for j in self.adjacencyList[i]: total_indegree[j] += 1 queue = [] for i in range(self.Vertices): if total_indegree[i] == 0: queue.append(i) visited_node = 0 order = [] while queue: u = queue.pop(0) order.append(u) for i in self.adjacencyList[u]: total_indegree[i] -= 1 if total_indegree[i] == 0: queue.append(i) visited_node += 1 if visited_node != self.Vertices: print("There's a cycle present in the Graph.\nGiven graph is not DAG") else: print(order) G = graph(6) G.createEdge(0,1) G.createEdge(0,2) G.createEdge(1,3) G.createEdge(1,5) G.createEdge(2,3) G.createEdge(2,5) G.createEdge(3,4) G.createEdge(5,4) G.topologicalSort()
输出
[0, 1, 2, 3, 5, 4]
拓扑排序算法的循环图
包含环的图无法进行拓扑排序，因为环图的依赖关系是循环的。例如，请查看以下图：
这个图不是有向无环图（DAG），因为 A、B 和 C 构成了一个环。仔细观察，你会发现没有入度为零的节点。根据 Kahn 算法，如果我们分析上面的图：
- 查找入度为零（无传入边）的节点。
- 从图中移除该节点并将其推入队列。然而，在上述图中，不存在入度为零的节点。每个节点的入度值都大于 0。
- 返回一个空队列，因为它找不到任何入度为零的节点。
我们可以使用拓扑排序来检测循环，步骤如下：
步骤1） 执行拓扑排序。
步骤2） 计算拓扑排序列表中元素的总数。
步骤3） 如果元素个数等于顶点总数，则不存在环。
步骤4） 如果它不等于顶点数，则给定的图数据结构中至少存在一个环。
拓扑排序的复杂性分析
算法的复杂度有两种类型，它们是：
- 时间复杂度
- 空间复杂度
这些复杂性用提供一般复杂性的函数来表示。
时间复杂度： 拓扑排序的时间复杂度在所有情况下都相同。时间复杂度存在最坏情况、平均情况和最佳情况。拓扑排序的时间复杂度为 O(E + V)，其中 E 表示图中的边数，V 表示图中的顶点数。
让我们突破这种复杂性：
步骤1） 首先，我们将计算所有入度。为此，我们需要遍历所有边，并且首先将所有 V 顶点的入度设置为零。因此，我们完成的增量步骤将是 欧拉(V+E).
步骤2） 我们将找到入度值为零的节点。我们需要从顶点的 V 号开始搜索。因此，完成的步骤将是 （V）.
步骤3） 对于每个入度为零的节点，我们将删除该节点并减少入度。对所有节点执行此操作将需要 欧氏距离.
步骤4） 最后，我们将检查是否存在循环。我们将检查排序数组中的元素总数是否等于节点总数。这将需要 O（1）.
因此，以上是拓扑排序或拓扑序化过程中每个步骤的时间复杂度。我们可以说，上述计算得出的时间复杂度为 O(V + E)；其中，O 表示复杂度函数。
空间复杂度： 运行拓扑排序算法需要 O(V) 个空间。以下是程序运行过程中需要空间的步骤：
- 我们必须计算图中所有节点的入度。由于图共有 V 个节点，因此我们需要创建一个大小为 V 的数组。因此，所需的空间为 （V）.
- 使用队列数据结构来存储入度为零的节点。我们从原始图中删除了入度为零的节点，并将其放入队列中。为此，所需空间为 （V）.
- 该数组名为“order”，用于按拓扑顺序存储节点。这也需要 （V） 空格。
这些是各个空间复杂度。因此，我们需要在运行时间内最大化这些空间。空间复杂度表示为 O(V)，其中 V 表示图中顶点的数量。
拓扑排序的应用
拓扑排序的应用非常广泛。以下列举一些应用场景：
- 它用于以下情况 Opera听系统 需要进行资源分配。
- 在图中寻找环。我们可以使用拓扑排序来验证图是否为有向无环图（DAG）。
- 自动完成应用程序中的句子排序。
- 它用于检测 僵局.
- 不同类型的日程安排或课程安排都使用拓扑排序。
- 解析依赖项。例如，如果您尝试安装一个包，该包可能还需要其他包。拓扑排序会找出安装当前包所需的所有包。
- Linux 使用“apt”中的拓扑排序来检查软件包的依赖关系。
