Python中拓扑排序的实现看起来简单，但实际上需要一定技巧。

Question

从这里提取出来的是一个最小化的迭代深度优先搜索程序，我称之为最小化是因为你几乎无法进一步简化代码：

def iterative_dfs(graph, start, path=[]):
    q = [start]
    while q:
        v = q.pop(0)
        if v not in path:
            path = path + [v]
            q = graph[v] + q

    return path

graph = {
    'a': ['b', 'c'],
    'b': ['d'],
    'c': ['d'],
    'd': ['e'],
    'e': []
}
print(iterative_dfs(graph, 'a'))

这是我的问题，你如何将此例程转换为一种拓扑排序方法，其中该例程也变得“最小化”？我看过这个video，这个想法非常聪明，所以我想知道是否可能将相同的技巧应用于上面的代码，以便topological_sort的最终结果也变得“最小”。不要求实现与上述例程不同的拓扑排序版本，我已经看过其中的几个。问题不是“如何在Python中实现拓扑排序”，而是找到使上述代码成为topological_sort所需的最小可能一组调整。

附加注释：

在原始文章中，作者说：

这个问题的目标不是优化iterative_dfs，而是从中得出一个最小版本的topological_sort（仅为了学习更多有关图论算法）。实际上，我想一个更普遍的问题可能是给定一组最小算法{iterative_dfs，recursive_dfs，iterative_bfs，recursive_dfs}，它们的topological_sort派生是什么？虽然这会使问题变得更长/复杂，但从iterative_dfs中找出topological_sort已经足够好了。

- BPL

---

也不要这样做：path=[]... - user3012759

@BPL - 抱歉我应该更清楚，path=[] 会在运行之间保留 [] 的值 - 这可能会让很多人感到惊讶... 只需使用相同的输入两次运行您的代码，并观察它产生不同的结果！ - user3012759

@BPL - 在这种情况下，它确实按预期工作，但仅因为另一个技术细节。带有 path = ... 的行将新列表分配给本地变量路径并返回该变量，但是如果将来的某个人更改为 path.append(v)，它会执行“相同的操作”，您将突然获得在调用之间保留值的 path - 通常不希望在Python中将可变对象作为默认参数。 - user3012759

@user3012759 好的，我现在明白你的观点了，我在某种程度上也同意...只要方法的后置条件是在函数调用的最终执行之后特定参数保持不变，算法就是正确的。现在，我们当然可以讨论是否使用默认参数作为使用局部变量的替代方案是一个好的实践，在这种情况下，我同意，因为你正在向公共接口添加无关的实现细节。 - BPL

@ShihabShahriar 我理解你为什么会这样问... 老实说，我在决定接受哪个答案时遇到了很多困难，因为它们都非常适合我。我之所以选择 Blckknght，主要是因为它获得了很多赞，而且它是第一个发布的，对于一般公众来说可能更有用，因为它提供了非常好的见解。另一方面，如果我们严格按照我制定的问题来看，我认为你的答案更加合适... 所以... 我不知道，也许我在挑选一个答案时做错了。两个答案都非常好，但我必须选择一个... - BPL

Answer 1

将DFS的迭代实现转换为拓扑排序并不容易，因为所需更改的变化与递归实现更加自然。但是你仍然可以做到，只需要实现自己的堆栈。

首先，这是您代码的稍微改进版本（更有效率，但不太复杂）：

def iterative_dfs_improved(graph, start):
    seen = set()  # efficient set to look up nodes in
    path = []     # there was no good reason for this to be an argument in your code
    q = [start]
    while q:
        v = q.pop()   # no reason not to pop from the end, where it's fast
        if v not in seen:
            seen.add(v)
            path.append(v)
            q.extend(graph[v]) # this will add the nodes in a slightly different order
                               # if you want the same order, use reversed(graph[v])

    return path

这是我修改代码进行拓扑排序的方式：

def iterative_topological_sort(graph, start):
    seen = set()
    stack = []    # path variable is gone, stack and order are new
    order = []    # order will be in reverse order at first
    q = [start]
    while q:
        v = q.pop()
        if v not in seen:
            seen.add(v) # no need to append to path any more
            q.extend(graph[v])

            while stack and v not in graph[stack[-1]]: # new stuff here!
                order.append(stack.pop())
            stack.append(v)

    return stack + order[::-1]   # new return value!

我在“new stuff here”的注释部分是关于如何在向上遍历堆栈时确定顺序的。它检查新找到的节点是否是前一个节点（位于堆栈顶部）的子节点。如果不是，则弹出堆栈顶部并将其值添加到order中。在进行深度优先搜索时，order将按照反向拓扑顺序排列，从最后一个值开始。我们在函数结尾处将其反转，并与已经按正确顺序排列的剩余堆栈值连接起来。

由于此代码需要多次检查v not in graph [stack [-1]]，因此如果graph字典中的值为集合而不是列表，则效率会更高。图通常不关心其边的顺序，因此进行这种更改不应该对大多数其他算法造成问题，尽管生成或更新图的代码可能需要修复。如果您打算扩展您的图形代码以支持带权重的图形，那么您可能最终会将列表更改为从节点映射到权重的字典，并且这也可以完美地运行（字典查找与集合查找一样为O(1)）。或者，如果无法直接修改 graph ，我们可以自己构建所需的集合。

供参考，以下是DFS的递归版本以及对其进行拓扑排序的修改。所需的修改非常小：

def recursive_dfs(graph, node):
    result = []
    seen = set()

    def recursive_helper(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                result.append(neighbor)     # this line will be replaced below
                seen.add(neighbor)
                recursive_helper(neighbor)

    recursive_helper(node)
    return result

def recursive_topological_sort(graph, node):
    result = []
    seen = set()

    def recursive_helper(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                recursive_helper(neighbor)
        result.insert(0, node)              # this line replaces the result.append line

    recursive_helper(node)
    return result

就这样！删除了一行，然后在不同的位置添加了一行类似的代码。如果您关心性能，您可能也应该在第二个辅助函数中使用result.append，并在顶层的recursive_topological_sort函数中执行return result[::-1]. 但是，使用insert(0, ...)是更简单的更改方式。

值得注意的是，如果您想要整个图的拓扑排序，您不需要指定起始节点。实际上，可能没有单个节点能让您遍历整个图，因此您可能需要进行几次遍历才能到达所有节点。在迭代式的拓扑排序中，让q初始化为list(graph)（所有图形键的列表），而不是一个只有单个起始节点的列表，这是一种轻松实现该目标的方法。对于递归版本，请将对recursive_helper(node)的调用替换为循环，如果它尚未在seen中，则在图中的每个节点上调用帮助函数。

- Blckknght

---

在迭代实现中，变量 q 实际上是一个栈。 - Saurabh

@Saurabh 是的，没错。原问题代码中的 q 变量也是一个栈，尽管它比较低效，因为它从开头推入和弹出，而不是列表在末尾具有高效操作。这就是使 DFS 成为 DFS 的原因。一个常规（LIFO）队列将给出广度优先遍历。然而，我们正在讨论的代码中并不值得注意的是那个 FIFO 队列。拓扑排序代码中命名为 stack 的栈替换了递归版本的调用栈。 - Blckknght

在递归深度优先搜索的实现中，result = [] 应该改为 result = [node]。 - Rushi Agrawal

Answer 2

我的想法基于两个关键观察：

1. 不要弹出堆栈中的下一个项，保留它以模拟堆栈展开。
2. 只推送一个孩子，而不是将所有孩子都推送到堆栈中。

这两个方法都有助于我们像递归dfs一样遍历图。正如其他答案所指出的那样，这对于这个特定问题非常重要。其余部分应该很容易。

def iterative_topological_sort(graph, start,path=set()):
    q = [start]
    ans = []
    while q:
        v = q[-1]                   #item 1,just access, don't pop
        path = path.union({v})  
        children = [x for x in graph[v] if x not in path]    
        if not children:              #no child or all of them already visited
            ans = [v]+ans 
            q.pop()
        else: q.append(children[0])   #item 2, push just one child

    return ans

q 是我们的栈。在主循环中，我们从栈中“访问”当前节点 v。这里使用“访问”，而不是“弹出”，因为我们需要能够再次回到该节点。我们找出当前节点的所有未访问子节点，并仅将第一个子节点推入栈中（q.append(children[0])），而不是一次性将它们全部推入。这正是递归深度优先搜索所做的事情。

如果没有找到符合条件的子节点（if not children），则我们已经访问完了其下的整个子树。因此，它已准备好被推入 ans 中。这时我们才真正将其弹出。

（当然，从性能上来看，这远非最佳方案。有几种相当简单的方式可以提高性能，但为了保持简单，我忽略了这些。）

- Shihab Shahriar Khan

---

这是一个很棒的方法！在概念上非常接近“纯”dfs！ - A.D

@StevenPenny，我不同意。 "有向图的拓扑排序是其顶点的线性排序，使得对于每个从顶点u到顶点v的有向边uv，u在排序中出现在v之前。" [维基链接] (https://en.wikipedia.org/wiki/Topological_sorting) - Shihab Shahriar Khan

在给定的示例中，我的解决方案输出：['a', 'c', 'b', 'd', 'e']，我认为这是期望的排序顺序，也是被接受的解决方案的排序顺序。 - Shihab Shahriar Khan

Answer 3

我对此还比较新，但是基于深度优先搜索的拓扑排序不应该无论从图中哪个点开始都能工作吗？当前的解决方案（截至本文撰写时）仅针对示例图中特定的起始点遍历整个图。（虽然我还没有完全思考清楚，但似乎问题出现在遇到没有相邻顶点可访问的顶点时。如果算法在遍历图中所有其他顶点之前遇到这样一个节点，则结果会被截断。）

虽然不像原帖所想的那样简单，但是以下是一种使用DFS的迭代式拓扑排序方法，可以在探索顶点的顺序不同的情况下正常工作。

```
from collections import deque

def iterative_top_sort(graph):
    result = deque() #using deque because we want to append left
    visited = set()

    #the first entry to the stack is a list of the vertices in the 
    #graph. 

    stack = [[key for key in graph]] #we want the stack to hold lists

    while stack:
      for i in stack[-1]: 
        if i in visited and i not in result: 
          result.appendleft(i)
        if i not in visited:
          visited.add(i)
          #add the vertex's neighbors to the stack
          stack.append(graph[i]) 
          break
      else: 
        stack.pop() 

    return result
```

- MooseCowBear

Answer 4

我也试图简化这个过程，所以想出了以下方法：

from collections import deque

def dfs(graph, source, stack, visited):
    visited.add(source)

    for neighbour in graph[source]:
        if neighbour not in visited:
            dfs(graph, neighbour, stack, visited)
    
    stack.appendleft(source)

def topological_sort_of(graph):
    stack = deque()
    visited = set()

    for vertex in graph.keys():
        if vertex not in visited:
            dfs(graph, vertex, stack, visited)

    return stack

if __name__ == "__main__":
    graph = {
        0: [1, 2],
        1: [2, 5],
        2: [3],
        3: [],
        4: [],
        5: [3, 4],
        6: [1, 5],
    }

    topological_sort = topological_sort_of(graph)
    print(topological_sort)

函数dfs（深度优先搜索）用于创建图中每个顶点的完成时间堆栈。这里的完成时间是指首先推入堆栈的元素，是所有邻居都被完全探索（没有其他未访问的邻居可从该顶点探索）的第一个顶点，而最后推入堆栈的元素则是所有邻居都被完全探索的最后一个顶点。

现在，堆栈就是拓扑排序。

使用Python集合作为visited提供了恒定的成员检查，并且使用deque作为堆栈提供了恒定时间的左插入。

这个高级想法是受到CLRS [1]的启发。

[1] Cormen, Thomas H.等人。算法导论。 MIT出版社，2009年。

- Rafael

Answer 5

给定您的示例图表：

a -->-- b -->-- d -->-- e
 \             /
  -->-- c -->--

我们需要实现这个图，你已经使用“从父节点到子节点”的方式完成了它：

graph = {
   'a': ['b', 'c'],
   'b': ['d'],
   'c': ['d'],
   'd': ['e'],
   'e': [],
}

但是你还需要提供一个start参数。在拓扑排序的上下文中，如果你提供了a，那么一切都很好：

[a, b, c, d, e]

但是如果您提供 b 呢？当前页面上的所有实现都会返回这个结果：

[b, d, e]

这是错误的，因为在执行d之前需要先执行c。为了解决这个问题，我们可以采用“子节点到父节点”的映射[1][2]。然后，我们可以选择一个end而不是选择一个start：

def tsort(graph, end):
   b = set()
   l = []
   s = [end]
   while s:
      n = s[-1]
      b.add(n)
      for m in graph[n]:
         if not m in b:
            s.append(m)
      if s[-1] == n:
         s.pop()
         l.append(n)
   return l

graph = {
   'a': [],
   'b': ['a'],
   'c': ['a'],
   'd': ['b', 'c'],
   'e': ['d'],
}

print(tsort(graph, 'e')) # ['a', 'c', 'b', 'd', 'e']

1. https://rosettacode.org/wiki/Topological_sort
2. https://github.com/adonovan/gopl.io/blob/master/ch5/toposort/main.go

- Zombo