Python BFS с коллекциями

Question

Я наткнулся на BFS-код , который включает в себя коллекции и запросы, но я не мог понять это много. Я надеюсь, что некоторые из питонистов здесь могут помочь n00b.

from collections import deque

def bfs(g, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])

Вопросы:

1) Оператор | =, похоже, связан с побитовыми операциями - я понятия не имею, как он относится к BFS, какие-либо подсказки?

2) popleft () должен возвращать только одно значение из того, что я понимаю, так как он возвращает parent и n здесь?

3) Является ли новым серией посещенных узлов? Если я хочу узлы, я просто продолжаю добавлять их в список?

Заранее спасибо.

Craig

Answer 1

1. a |= b для наборов совпадает с a = a.union(b).

2. popleft() действительно возвращает только один элемент, который оказывается 2-tuple, и, следовательно, может быть распакован в два значения.

3. new - набор еще не посещенных узлов.

Answer 2

Просто чтобы ответить на ваш последний вопрос: у вас есть кусок кода генератор , что означает, что он выдает узлы при прохождении графика в ширину.Он не выполняет никакого реального поиска, он просто пересекает узел для вас.То, как вы используете этот фрагмент кода, заключается в переборе результатов, что даст вам все узлы по очереди (в порядке ширины):

for parent_node, node in bfs(my_graph):
    if node == needle:
        break

Или, если вы хотите, например, списоквсех узлов, соответствующих определенному условию:

nodes = [ node for parent_node, node in bfs(my_graph) if condition(node) ]

Answer 3

1)

x |= y устанавливает x в логическое ИЛИ для x и y.set переопределяет оператор для обозначения объединенного множества.По сути, это причудливый способ записи enqueued.update(new).

2)

Первый элемент queue всегда представляет собой 2-кортеж.

tpl = (a,b)
x,y = tpl

причудливый способ записи

tpl = (a,b)
assert len(tpl) == 2
x = tpl[0]
y = tpl[0]

3)

new - это просто временная переменная для - ну - новых (не посещенных) узлов.enqueued содержит результат.