我正在 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)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)