BPL*_*BPL 19 python algorithm graph-theory depth-first-search topological-sort
从这里提取我们得到了一个最小的迭代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'))
这是我的问题,您如何将此例程转换为拓扑排序方法,其中例程也变为"最小"？我看过这个视频,这个想法非常聪明,所以我想知道是否可以在上面的代码中应用相同的技巧,所以topological_sort的最终结果也变得"最小".
不要求拓扑排序的版本,这不是对上述例程的微小修改,我已经看过很少.问题不是"如何在python中实现拓扑排序",而是找到上述代码的最小可能调整集成为topological_sort.
附加评论
在原文中,作者说:
不久之前,我读了Guido van Rossen的图表实现,看似简单.现在,我坚持使用复杂性最低的纯python最小系统.我们的想法是能够探索算法.稍后,您可以优化和优化代码,但您可能希望以编译语言执行此操作.
这个问题的目标不是优化iterative_dfs,而是提出一个从它派生的topology_sort的最小版本(只是为了更多地了解图论算法).其实,我想一个更一般的问题可以像给一组最小的算法,{ iterative_dfs,recursive_dfs,iterative_bfs,recursive_dfs},这将是他们的topological_sort推导？虽然这会使问题变得更长/更复杂,但是从iterative_dfs中找出topology_sort就足够了.
Blc*_*ght 23
将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!
我在这里评论"新东西"的部分是在向上移动时计算出顺序的部分.它检查找到的新节点是否是前一个节点(位于堆栈顶部)的子节点.如果没有,它会弹出堆栈的顶部并将值添加到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在第二个辅助函数中做,并return result[::-1]在顶级recursive_topological_sort函数中做.但使用insert(0, ...)是一个更小的变化.
值得注意的是,如果您需要整个图的拓扑顺序,则不需要指定起始节点.实际上,可能没有一个节点可以让您遍历整个图形,因此您可能需要进行多次遍历以获取所有内容.在迭代拓扑排序中实现这种情况的一种简单方法是初始化q为list(graph)(所有图形键的列表),而不是仅包含单个起始节点的列表.对于递归版本,将调用替换为recursive_helper(node)在图中的每个节点上调用辅助函数的循环(如果尚未存在)seen.
我的想法基于两个主要观察结果:
这两个都帮助我们完全像递归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从堆栈"访问"当前节点.'access',而不是'pop',因为我们需要能够再次返回此节点.我们找到了当前节点的所有未访问过的子节点.并且只将第一个推送到stack(q.append(children[0])),而不是将它们全部放在一起.同样,这正是我们对递归dfs所做的.
如果找不到符合条件的孩子(if not children),我们访问了它下面的整个子树.所以它已经准备好被推入ans.这就是我们真正流行的时候.
(不言而喻,它在性能方面并不是很好.不是在children变量中生成所有未访问的子项,而是生成第一个,生成器样式,可能使用过滤器.我们也应该反转它ans = [v] + ans并在最后调用reverseon ans.但是OP坚持简单,省略了这些事情.)