使用collections进行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) |= 这个操作符好像和位运算有关，但我不知道它和广度优先搜索有什么关系，有什么提示吗？

2) 我理解 popleft() 应该只返回一个值，那它是怎么同时返回父节点和 n 的呢？

3) new 是不是表示访问过的节点系列？如果我想要节点，是不是只需要把它们一个个加到列表里就行了？

提前谢谢大家。

Craig

Answer 1

1)

x |= y 这个操作是把 x 设置为 x 和 y 的布尔“或”结果。这里的 set 是用来表示集合的合并。简单来说，这就是在说 enqueued.update(new) 的一种更复杂的写法。

2)

队列中的第一个元素总是一个包含两个值的元组。

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

这是一种更复杂的写法

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

3)

new 只是一个临时变量，用来表示那些新的（还没访问过的）节点。而 enqueued 则包含了最终的结果。

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. a |= b 对于集合来说，和 a = a.union(b) 是一样的意思。

2. popleft() 确实只返回一个元素，这个元素是一个包含两个值的元组，所以可以把它拆分成两个值。

3. new 是指那些还没有被访问过的节点。