python-3.x - 在 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)
推荐阅读
- ios - 如何从核心数据中获取子实体值?
- javascript - 当我单击按钮时,我的功能确实有效(Angular 2)
- c# - 为什么 System.IO.File.AppendAllText 会锁定我的文件?
- excel-formula - 基于真/假值消除行的公式(不留下空白行)
- linux - AWS CLI:找不到配置文件(示例)
- java - 无法为 webdrivermanger 使用 git 个人访问令牌?
- json - 使用 JQ 将 Winston JSON 日志输出到 CSV,但出现“不能通过 Csv 格式化,仅数组”错误
- angular - Angular ViewChildren 不会立即看到来自 ngFor 的所有孩子
- c++ - 在调用者和被调用者中共享pointee不一样
- c# - 在 sql asp.net 中获取过去 30 天未登录的用户