python中拓扑排序的看似简单的实现 [英] deceptively simple implementation of topological sorting in python
问题描述
从此处中提取的内容迭代dfs例程，我称其为最小，因为您几乎无法进一步简化代码：
Extracted from here we got a minimal iterative dfs routine, i call it minimal because you can hardly simplify the code further:
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'))
这是我的问题，如何将这个例程转换为拓扑排序方法，使例程也变为最小？我已经看过这部视频，这个主意非常聪明，所以我当时想知道是否有可能将相同的技巧应用到上面的代码中，因此topologic_sort的最终结果也变为最小。
Here's my question, how could you transform this routine into a topological sort method where the routine also becomes "minimal"? I've watched this video and the idea is quite clever so I was wondering if it'd be possible to apply the same trick into the above code so the final result of topological_sort also becomes "minimal".
不要求提供拓扑版本排序不是对上面例程的微小修改，我已经很少看到它们了。问题不是我如何在python中实现拓扑排序，而是找到上述代码的最小调整集，以成为 topological_sort 。
Not asking for a version of topological sorting which is not a tiny modification of the above routine, i've already seen few of them. The question is not "how do i implement topological sorting in python" but instead, finding the smallest possible set of tweaks of the above code to become a topological_sort.
附加评论
在原始文章中，作者说：
In the original article the author says :
前一段时间，我读过Guido van Rossen的图形实现，认为
看起来很简单。现在，我坚持使用最低复杂度的纯Python最小系统
。这个想法是为了能够探索
算法。稍后，您可以优化和优化代码，但是
可能希望使用编译语言来完成此操作。
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派生是什么？尽管这会使问题变得更加冗长/复杂，但是从iterative_dfs中找出topological_sort就足够了。
The goal of this question is not optimizing iterative_dfs but instead coming up with a minimal version of topological_sort derived from it (just for the sake of learning more about graph theory algorithms). In fact, i guess a more general question could be something like given the set of minimal algorithms, {iterative_dfs, recursive_dfs, iterative_bfs, recursive_dfs}, what would be their topological_sort derivations? Although that would make the question more long/complex, so figuring out the topological_sort out of iterative_dfs is good enough.
推荐答案
易于将DFS的迭代实现转换为拓扑类型，因为对于递归实现而言，需要进行的更改更加自然。但是，您仍然可以这样做，只需要实现自己的堆栈即可。
It's not easy to turn an iterative implementation of DFS into Topological sort, since the change that needs to be done is more natural with a recursive implementation. But you can still do it, it just requires that you implement your own stack.
首先，这是代码的稍微改进的版本（效率更高，而不是
First off, here's a slightly improved version of your code (it's much more efficient and not much more complicated):
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
这是我修改该代码以进行拓扑排序的方式：
Here's how I'd modify that code to do a topological sort:
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!
我在这里有新东西评论的部分是确定移动顺序的部分在堆栈上。它检查找到的新节点是否是先前节点的子节点（位于堆栈顶部）。如果不是，它将弹出堆栈的顶部，并将值添加到 order 。在执行DFS时， order 的顺序将是反向的，从最后一个值开始。我们在函数末尾将其取反，并将其与堆栈上的其余值（方便地已经按正确的顺序）连接起来。
The part I commented with "new stuff here" is the part that figures out the order as you move up the stack. It checks if the new node that's been found is a child of the previous node (which is on the top of the stack). If not, it pops the top of the stack and adds the value to order. While we're doing the DFS, order will be in reverse topological order, starting from the last values. We reverse it at the end of the function, and concatenate it with the remaining values on the stack (which conveniently are already in the correct order).
因为此代码需要多次检查 v是否不在graph [stack [-1]] 中，如果 graph 字典是集合，而不是列表。图表通常并不关心边缘的保存顺序，因此，即使生成或更新图表的代码可能需要修复，进行此类更改也不会导致大多数其他算法出现问题。如果您打算扩展图形代码以支持加权图形，则可能最终还是将列表更改为从节点映射到权重的字典，这对于此代码同样适用（字典查找 O（1）就像设置查找一样）。或者，如果不能直接修改图，我们可以构建自己需要的集合。
Because this code needs to check v not in graph[stack[-1]] a bunch of times, it will be much more efficient if the values in the graph dictionary are sets, rather than lists. A graph usually doesn't care about the order its edges are saved in, so making such a change shouldn't cause problems with most other algorithms, though code that produces or updates the graph might need fixing. If you ever intend to extend your graph code to support weighted graphs, you'll probably end up changing the lists to dictionaries mapping from node to weight anyway, and that would work just as well for this code (dictionary lookups are O(1) just like set lookups). Alternatively, we could build the sets we need ourselves, if graph can't be modified directly.
供参考，这是DFS的递归版本，并对它进行了修改以进行拓扑排序。确实需要的修改很小：
For reference, here's a recursive version of DFS, and a modification of it to do a topological sort. The modification needed is very small indeed:
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 ，并执行 return result [::-1] 在顶级 recursive_topological_sort 函数中。但是使用 insert（0，...）是一个更小的更改。
That's it! One line gets removed and a similar one gets added at a different location. If you care about performance, you should probably do result.append in the second helper function too, and do return result[::-1] in the top level recursive_topological_sort function. But using insert(0, ...) is a more minimal change.
它还值得注意的是如果您需要整个图的拓扑顺序，则无需指定起始节点。确实，可能没有单个节点可以遍历整个图，因此您可能需要进行多次遍历才能遍历所有内容。实现迭代拓扑排序的一种简单方法是将 q 初始化为 list（graph）（一个列表图的所有键），而不是仅包含一个起始节点的列表。对于递归版本，将对 recursive_helper（node）的调用替换为一个循环，该循环将调用图中每个节点上的helper函数（如果尚未位于
Its also worth noting that if you want a topological order of the whole graph, you shouldn't need to specify a starting node. Indeed, there may not be a single node that lets you traverse the entire graph, so you may need to do several traversals to get to everything. An easy way to make that happen in the iterative topological sort is to initialize q to list(graph) (a list of all the graph's keys) instead of a list with only a single starting node. For the recursive version, replace the call to recursive_helper(node) with a loop that calls the helper function on every node in the graph if it's not yet in seen.
这篇关于python中拓扑排序的看似简单的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
