python-3.x - 在 Python 中使用生成器进行广度优先树遍历

Question

我正在学习如何在 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”方法。

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

Answer 1

如果没有一些严重的 hack，你不能为 bfs 使用递归(堆栈)，但是队列可以工作:

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