在Python中使用生成器进行广度优先树遍历

本文介绍了在Python中使用生成器进行广度优先树遍历的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在研究如何在David Beazly的优秀Python Cookbook文本中使用Python中的生成器。下面的代码配方非常优雅地使用生成器定义了深度优先树遍历：

# example.py # # Example of depth-first search using a generator class Node: def __init__(self, value): self._value = value self._children = [] def __repr__(self): return 'Node({!r})'.format(self._value) def add_child(self, node): self._children.append(node) def __iter__(self): return iter(self._children) def depth_first(self): yield self for c in self: yield from c.depth_first() # Example if __name__ == '__main__': root = Node(0) child1 = Node(1) child2 = Node(2) root.add_child(child1) root.add_child(child2) child1.add_child(Node(3)) child1.add_child(Node(4)) child2.add_child(Node(5)) for ch in root.depth_first(): print(ch) # Outputs: Node(0), Node(1), Node(3), Node(4), Node(2), Node(5)

我正在努力想出一个同样优雅的方法

def breadth_first(self): pass

我故意不张贴我一直在尝试的疯狂的东西，因为我尝试的每一件事都需要保持"状态"。我不想使用传统的基于队列的解决方案。本学术练习的全部目的是深入了解生成器的行为。因此，我希望使用上面树的生成器创建一个并行的"breadth_first"方法。

欢迎任何指针/解决方案。

推荐答案

您无法对bfs使用递归(堆栈)，除非遇到一些严重的黑客攻击，但是队列可以工作：

def breadth_first(self): q = [self] while q: n = q.pop(0) yield n for c in n._children: q.append(c)