河小马
排序是计算机科学中的一个基本概念，它帮助我们更好地理解和处理数据。虽然通常按升序或降序进行排序很常见，但有时这并不适用于我们的情况。当我们需要突出元素之间的关系或说明过程的顺序步骤时，根据它们的相对依赖关系对数据值进行排序是很有用的。实现这一点的方法之一是通过拓扑排序算法。在本文中，我们将解释拓扑排序的工作原理、实现方法和应用场景。
什么是拓扑排序？
在计算机科学中，拓扑表示图中节点的排列和连接，这些节点代表元素。我们使用拓扑排序处理有向无环图（dag），其中节点以特定方向连接。也不存在循环，这意味着我们不能通过某些有向边的组合遍历并最终到达同一个顶点。
拓扑排序的基本思想是找到节点之间的逻辑顺序。元素被安排在每个有向边在逻辑上从前面的元素指向后面的元素。我们还可以描述为仅在所有直接指向它的节点都被访问后才访问一个节点。拓扑排序可以使用深度优先搜索（dfs）或广度优先搜索（bfs）实现，具体取决于您的需求。接下来让我们分别来看看这两种方法。
基于dfs的拓扑排序
顾名思义，dfs通过优先考虑“深度”来工作，这意味着它会在继续到另一个分支之前尽可能深入地探索一个顶点的一条分支。通过跟踪已访问和未访问的节点，我们可以使用dfs来识别图中的循环并找到连接，或者在这种情况下进行拓扑排序。
我们可以将伪代码分解如下：
function topologicalsortdfs(graph):
visited = []
stack = []
对于图中的每个顶点:
如果顶点未被访问：
dfs(顶点, visited, stack, graph)
返回 stack 的反转
function dfs(顶点, visited, stack, graph):
将顶点标记为已访问
对于图[顶点]中的每个邻居：
如果邻居未被访问：
dfs(邻居, visited, stack, graph)
将顶点推入 stack首先，我们必须定义排序函数，并使用列表来跟踪已访问的节点。我们还必须实现一个堆栈结构来以相反顺序存储排序后的节点。这是因为堆栈按照后进先出（lifo）原则工作，意味着最后访问的顶点将添加到堆栈的顶部。因此，我们必须反转顺序以获取正确的顺序。
我们使用for循环遍历每个顶点。如果顶点尚未被访问，则对其执行dfs算法。此算法接受当前顶点、已访问顶点列表、堆栈和图作为参数。我们还对每个未被访问的邻居顶点执行算法。完成后，我们将顶点推入堆栈。
最后，我们按照前面提到的方式翻转得到的堆栈，以获得拓扑排序。
示例实现
对于一个简单的例子，考虑以下图：
这是一个简单的、有向的、非循环图。
©jingzhengli.com
这里有5个节点 – a，b，c，d和e。这是一个有向图，每个节点都指向另一个节点，除了节点b和c。我们可以按照以下方法在python中使用dfs进行拓扑排序：
def dfs_topological_sort(graph):
visited = set()
stack = []
def dfs(vertex):
visited.add(vertex)
if vertex in graph:
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor)
stack.append(vertex)
for vertex in graph:
if vertex not in visited:
dfs(vertex)
return stack[::-1]
graph = {
'c': ['d', 'a'],
'd': ['a', 'b'],
'a': ['b', 'e']
}
sorted_vertices = dfs_topological_sort(graph)
print(sorted_vertices)如前所述，我们定义了算法”dfs_topological_sort”，并实现了一个列表和一个堆栈。
dfs函数的第一行将当前顶点添加到visited列表中。然后为该顶点的每个未被访问的邻居调用dfs。然后将顶点添加到堆栈中，并访问其他顶点。我们在最后将图数据作为字典输入，调用sort函数，并打印排序后的顶点。我们可以在下面的图像中按顺序看到这些顶点[c，d，a，e，b]。
此bfs代码示例的结果是”[‘c’, ‘d’, ‘a’, ‘e’, ‘b’]”，显示在底部。
©jingzhengli.com
基于bfs的拓扑排序
实现拓扑排序的另一种方法是使用bfs算法。与先完全探索深度优先分支不同，bfs通过在每个“层级”的节点上进行探索，然后向下移动一层来工作。我们使用一个队列而不是堆栈来跟踪访问的顶点。
我们可以将此方法的伪代码写如下：
function topologicalsortbfs(graph):
indegree = {}
queue = []
result = []
for each vertex in graph:
indegree[vertex] = 0
for each vertex in graph:
for each neighbor in graph[vertex]:
indegree[neighbor] += 1
for each vertex in graph:
if indegree[vertex] == 0:
add vertex to queue
while queue is not empty:
current = remove vertex from front of queue
add current to result list
for each neighbor in graph[current]:
decrement in-degree of neighbor
if in-degree of neighbor becomes 0:
add neighbor to queue
return result与之前一样，我们定义了函数。这次，我们使用一个字典来存储每个节点的入度值。这些值简单地是指向该节点的有向边的数量。我们还初始化了一个空队列和一个列表来存储结果。
然后使用三个循环来迭代每个顶点。第一个将入度值设置为0，第二个增加每个相邻顶点的这个值。第三个循环将入度值为0的每个顶点添加到队列中以进行处理。
while循环从队列的前面删除没有依赖关系的顶点以进行处理。然后将其添加到排序列表中，并将其邻居的入度减1。入度为0的邻居然后被添加到队列中。
示例实现
使用相同的例子，下面是使用bfs实现拓扑排序的代码块：
from collections import deque
def bfs_topological_sort(graph):
indegree = {}
queue = deque()
result = []
for vertex in graph:
indegree[vertex] = 0
for vertex in graph:
for neighbor in graph[vertex]:
indegree[neighbor] += 1
for vertex in graph:
if indegree[vertex] == 0:
queue.append(vertex)
while queue:
current = queue.popleft()
result.append(current)
for neighbor in graph[current]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return result
graph = {
'c': ['d', 'a'],
'd': ['a', 'b'],
'a': ['b', 'e'],
'b': [],
'e': []
}
sorted_vertices = bfs_topological_sort(graph)
print(sorted_vertices)首先，我们必须实现“deque”类，它允许我们使用双端队列作为数据结构。
然后我们定义bfs函数“bfs_topological_sort”，它以“graph”作为输入。接下来，我们创建一个空字典“indegree”，一个空队列“queue”和一个空列表“list”。
第一个for循环将每个节点添加为字典的键。接下来的两个循环计算入度，并将入度为0的节点添加到队列中。
然后，根据while循环删除顶点，并将排序后的顶点添加到排序列表中，直到队列为空。一旦依赖关系为0，就会探索相邻节点。
最后，与之前一样，我们输入我们的图形数据，调用函数并打印排序后的顶点列表。我们可以在图像中看到输出。
请注意，bfs的结果[c，d，a，b，e]与dfs的结果[c，d，a，e，b]不同。这是因为两种算法的工作方式不同。因为dfs是通过尽可能深入一个分支来探索的，所以它在回溯之前访问a和e，最后访问b。然而，bfs在向下移动之前访问每个级别的节点。因此，它仍然在d之后访问a，但是b与a处于相同的深度级别，所以它在e之前访问b。
该bfs代码示例的结果是“[‘c'，'d'，'a'，'b'，'e']”，如底部所示。
©jingzhengli.com
拓扑排序的应用
由于拓扑排序在需要逻辑顺序的情况下非常有用，它可以用于许多需要按特定顺序进行任务或事件的应用程序。这可以是像根据食谱烹饪的简单事情，其中某些指令必须在其他指令之前（例如，在将蛋糕糊搅拌均匀之前将其倒入模具中）。通常，拓扑排序用于处理围绕工作流和任务调度的更复杂情况。如果我们管理一个项目，构建一个程序，甚至组织学生的课程，某些元素必须在整个过程中先于其他元素。这些都是拓扑排序可以帮助的情况。
拓扑排序的复杂度
拓扑排序的时间和空间复杂度取决于实现方式，但对于dfs和bfs，我们可以认为它们是相同的。无论使用哪个函数，我们都必须访问图的每个顶点和边。因此，时间复杂度为o(v + e)，与顶点数（v）和边数（e）成比例。
在空间复杂度方面，两种算法的复杂度都为o(v)，因为我们需要在堆栈和队列中存储访问过的顶点。因此，复杂度与顶点数成正比。
总结
总之，拓扑排序是一种根据任务或事件的依赖关系和逻辑顺序来组织的众所周知的方法。它在计算机科学领域以及各种组织中被广泛使用，以优化工作流程和安排任务和课程。无论您是在处理图形还是解决效率问题，拓扑排序都可能会派上用场。
