Ширина первого обхода дерева с использованием генераторов в Python - PullRequest
Новая
       46

Ширина первого обхода дерева с использованием генераторов в Python

0 голосов
/ 12 мая 2018

Я изучаю, как использовать Генераторы в Python, в превосходном тексте Дэвида Бизли «Python Cookbook». Следующий рецепт кода очень элегантно определяет глубину первого обхода дерева, используя генераторы: 

# 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, используя генераторы для дерева выше.

Любые указатели / решения приветствуются.

1 Ответ

0 голосов
/ 12 мая 2018

Вы не можете использовать рекурсию (стек) для bfs без серьезных взломов, но очередь будет работать: 

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