Python BFS與集合

我碰到一個BFS code其中涉及集合和deques，但我不明白它太多。我希望這裏的一些pythonistas能幫助你解決問題。Python BFS與集合

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）是否新該系列節點訪問過？如果我需要這些節點，我是否會將它們附加到列表中？

在此先感謝。

克雷格

來源

2011-05-25 Craig

a |= b爲集是相同的作爲a = a.union(b)。
popleft()確實返回只有一個元件，這恰好是2元組，並且因此可以是解壓成兩個值。
new是尚未設置訪問節點。

來源

2011-05-25 12:38:11 pillmuncher

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-25 12:39:45 phihag

只是爲了回答你的最後一個問題：你在那裏的代碼片段是生成器，這意味着當它橫跨圖的寬度優先時它產生節點。它不做任何實際的搜索，它只是爲你遍歷節點。您使用這段代碼的方式是通過循環的結果，這將給你又將所有節點（在廣度優先的順序）：

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-25 12:41:52

Python BFS與集合

回答

相關問題