python 中看似简单的拓扑排序实现
deceptively simple implementation of topological sorting in python
从 here 中提取我们得到了一个最小的迭代 dfs 例程，我称它为最小的因为你很难进一步简化代码：
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'))
我的问题是，如何将此例程转换为拓扑排序方法，例程也变为 "minimal"？我看过这个 video 并且这个想法非常聪明所以我想知道是否可以将相同的技巧应用到上面的代码中所以 topological_sort 的最终结果也变成 "minimal".
不要求拓扑排序的版本，它不是对上述例程的微小修改，我已经看到了其中的一些。问题不是 "how do i implement topological sorting in python"，而是找到上述代码的最小可能调整集以成为 topological_sort.
补充评论
作者在原文中说：
A while ago, I read a graph implementation by Guido van Rossen that
was deceptively simple. Now, I insist on a pure python minimal system
with the least complexity. The idea is to be able to explore the
algorithm. Later, you can refine and optimize the code but you will
probably want to do this in a compiled language.
这个问题的目的不是优化 iterative_dfs，而是想出一个从中派生出的 topological_sort 的最小版本（只是为了更多地了解图论算法）。事实上，我想一个更一般的问题可能是给定一组最小算法，{iterative_dfs、recursive_dfs、iterative_bfs、recursive_dfs}，他们会是什么topological_sort 推导？虽然这会使问题变得更 long/complex，所以从 iterative_dfs 中找出 topological_sort 就足够了。
将 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。当我们进行 DFS 时，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.
中）
我的想法基于两个主要观察结果：
- 不要从堆栈中弹出下一项，保留它以模拟堆栈展开。
- 与其将所有 children 压入堆栈，不如压入一个。
这两个都帮助我们像递归 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 这是我们的堆栈。在主循环中，我们 'access' 来自堆栈的当前节点 v 。 'access'，不是'pop'，因为我们需要能够再次回到这个节点。我们找出当前节点所有未访问的children。并仅将第一个推入堆栈 (q.append(children[0]))，而不是将所有推入堆栈。同样，这正是我们对递归 dfs 所做的。
如果没有找到符合条件的child(if not children)，我们已经访问了它下面的整个子树。所以它已准备好被推入 ans。这就是我们真正弹出它的时候。
（当然，这远非最优 - performance-wise。有几种相当简单的方法可以提高性能，但为了简单起见，我忽略了这些。）
我也试图简化这个所以我想到了这个：
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（深度优先搜索）用于为图中的每个顶点创建完成时间堆栈。此处的完成时间意味着元素首先被推入堆栈，是第一个顶点，其所有邻居都被完全探索（没有其他未访问的邻居可用于从该顶点探索）并且最后一个被推入堆栈的元素是最后一个顶点充分探索其所有邻居的地方。
堆栈现在只是简单的拓扑排序。
为 visited 使用 Python 集提供常量成员检查，使用 deque 作为堆栈也提供 constant-time 左插入。
high-level 的想法受到 CLRS [1] 的启发。
[1] Cormen、Thomas H. 等人。算法简介。麻省理工学院出版社，2009.
鉴于您的示例图：
a -->-- b -->-- d -->-- e
\ /
-->-- c -->--
我们需要实现您使用“parent to children”完成的图形：
graph = {
'a': ['b', 'c'],
'b': ['d'],
'c': ['d'],
'd': ['e'],
'e': [],
}
但您还提供了一个 start 参数。在拓扑排序的上下文中，
如果你提供 a，那么一切都很好：
[a, b, c, d, e]
但是如果您提供 b 会怎样？当前此页面上的所有实现
return 这个：
[b, d, e]
不正确，因为 c 需要在 d 之前完成。解决
为此，我们可以改为将“child 映射到 parents”[1][2]。然后而不是选择一个
start 我们可以选择一个 end:
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']
我对此很陌生，但是无论从图中的哪个位置开始，基于 DFS 的拓扑排序都不应该起作用吗？当前的解决方案（截至撰写本文时）仅针对示例图中的特定起点遍历整个图。 （虽然我还没有完全考虑清楚，但问题似乎发生在命中一个没有邻居可访问的顶点时。如果算法在遍历图中所有其他顶点之前命中这样一个节点，那么结果将被截断。 )
尽管它并不像 OP 可能希望的那么简单，但以下是使用 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
```
从 here 中提取我们得到了一个最小的迭代 dfs 例程，我称它为最小的因为你很难进一步简化代码：
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'))
我的问题是，如何将此例程转换为拓扑排序方法，例程也变为 "minimal"？我看过这个 video 并且这个想法非常聪明所以我想知道是否可以将相同的技巧应用到上面的代码中所以 topological_sort 的最终结果也变成 "minimal".
不要求拓扑排序的版本，它不是对上述例程的微小修改，我已经看到了其中的一些。问题不是 "how do i implement topological sorting in python"，而是找到上述代码的最小可能调整集以成为 topological_sort.
补充评论
作者在原文中说：
A while ago, I read a graph implementation by Guido van Rossen that was deceptively simple. Now, I insist on a pure python minimal system with the least complexity. The idea is to be able to explore the algorithm. Later, you can refine and optimize the code but you will probably want to do this in a compiled language.
这个问题的目的不是优化 iterative_dfs，而是想出一个从中派生出的 topological_sort 的最小版本（只是为了更多地了解图论算法）。事实上，我想一个更一般的问题可能是给定一组最小算法，{iterative_dfs、recursive_dfs、iterative_bfs、recursive_dfs}，他们会是什么topological_sort 推导？虽然这会使问题变得更 long/complex，所以从 iterative_dfs 中找出 topological_sort 就足够了。
将 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。当我们进行 DFS 时，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.
我的想法基于两个主要观察结果：
- 不要从堆栈中弹出下一项，保留它以模拟堆栈展开。
- 与其将所有 children 压入堆栈，不如压入一个。
这两个都帮助我们像递归 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 这是我们的堆栈。在主循环中，我们 'access' 来自堆栈的当前节点 v 。 'access'，不是'pop'，因为我们需要能够再次回到这个节点。我们找出当前节点所有未访问的children。并仅将第一个推入堆栈 (q.append(children[0]))，而不是将所有推入堆栈。同样，这正是我们对递归 dfs 所做的。
如果没有找到符合条件的child(if not children)，我们已经访问了它下面的整个子树。所以它已准备好被推入 ans。这就是我们真正弹出它的时候。
（当然，这远非最优 - performance-wise。有几种相当简单的方法可以提高性能，但为了简单起见，我忽略了这些。）
我也试图简化这个所以我想到了这个：
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（深度优先搜索）用于为图中的每个顶点创建完成时间堆栈。此处的完成时间意味着元素首先被推入堆栈，是第一个顶点，其所有邻居都被完全探索（没有其他未访问的邻居可用于从该顶点探索）并且最后一个被推入堆栈的元素是最后一个顶点充分探索其所有邻居的地方。
堆栈现在只是简单的拓扑排序。
为 visited 使用 Python 集提供常量成员检查，使用 deque 作为堆栈也提供 constant-time 左插入。
high-level 的想法受到 CLRS [1] 的启发。
[1] Cormen、Thomas H. 等人。算法简介。麻省理工学院出版社，2009.
鉴于您的示例图：
a -->-- b -->-- d -->-- e
\ /
-->-- c -->--
我们需要实现您使用“parent to children”完成的图形：
graph = {
'a': ['b', 'c'],
'b': ['d'],
'c': ['d'],
'd': ['e'],
'e': [],
}
但您还提供了一个 start 参数。在拓扑排序的上下文中，
如果你提供 a，那么一切都很好：
[a, b, c, d, e]
但是如果您提供 b 会怎样？当前此页面上的所有实现
return 这个：
[b, d, e]
不正确，因为 c 需要在 d 之前完成。解决
为此，我们可以改为将“child 映射到 parents”[1][2]。然后而不是选择一个
start 我们可以选择一个 end:
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']
我对此很陌生，但是无论从图中的哪个位置开始，基于 DFS 的拓扑排序都不应该起作用吗？当前的解决方案（截至撰写本文时）仅针对示例图中的特定起点遍历整个图。 （虽然我还没有完全考虑清楚，但问题似乎发生在命中一个没有邻居可访问的顶点时。如果算法在遍历图中所有其他顶点之前命中这样一个节点，那么结果将被截断。 )
尽管它并不像 OP 可能希望的那么简单，但以下是使用 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
```