0

我遇到了一个涉及集合和双端队列的BFS 代码，但我不太理解。我希望这里的一些pythonistas可以帮助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)访问的节点系列是新的吗？如果我想要节点，我是否只是继续将它们附加到列表中？

提前致谢。

克雷格

4

3 回答 3

2

  1. a |= b对于集合是一样的a = a.union(b)。

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

  3. new是尚未访问的节点的集合。

于 2011-05-25T12:38:11.343 回答
1

只是为了回答您的最后一个问题：您拥有的代码有一个generator，这意味着它在遍历图广度优先时会产生节点。它不进行任何实际搜索，它只是为您遍历节点。您使用这段代码的方式是遍历结果，这将依次为您提供所有节点（按广度优先顺序）：

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) ]
于 2011-05-25T12:41:52.707 回答
0

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包含结果。

于 2011-05-25T12:39:45.933 回答