Python BFS 与集合

Question

我遇到了 BFS 代码，其中涉及集合和双端队列，但我不太理解。我希望这里的一些 Python 爱好者可以帮助新手。

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) 访问的一系列节点是新的吗？如果我想要这些节点，我是否只需将它们附加到列表中？

提前致谢。

克雷格

Answer 1

1. a |= b 对于集合来说是相同的
   对于集合来说 a = a.union(b).

2. popleft() 确实返回
   只有一个元素，恰好
   是一个 2 元组，因此可以是
   解压缩为两个值。

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 的布尔 OR。 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 包含结果。