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()は、私が理解していることから 1 つの値のみを返す必要があるため、ここで親と n を返す方法は?

3)訪問した一連のノードは新しいですか? ノードが必要な場合は、それらをリストに追加し続けますか?

前もって感謝します。

クレイグ

4

3 に答える 3

2

  1. a |= bfor セットは と同じa = a.union(b)です。

  2. popleft()実際には 1 つの要素のみを返しますが、これはたまたま 2 タプルであるため、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 |= yx を 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 に答える