BFS アルゴリズムの原理の詳細な分析、図解付きの説明、および BFS アルゴリズムを実装するための Python コード。

BFS (幅優先検索とも呼ばれます) は、DFS アルゴリズムと同様の再帰的アルゴリズムです。違いは、BFS アルゴリズムではキューを使用して、ループを回避しながらすべてのターゲット ノードを走査することです。

BFS アルゴリズムの動作原理の説明

以下に示すように、5 つのノードを持つ無向グラフを例に挙げます。

# ノード 0 から開始して、BFS アルゴリズムはまずノード 0 を訪問済みリストに入れ、その隣接するすべてのノードをキューに入れます。

#次に、キューの先頭にあるノード 1 にアクセスし、ノード 1 に隣接するノードに移動します。ノード 0 はすでに訪問されているため、ノード 2 が訪問されます。

#ノード 2 には未訪問の隣接ノード 4 がありますが、ノード 4 はキューの最後尾にあるため、ノード 4 の先頭にアクセスする必要があります。最初にノード 3 をキューに入れます。

#ノード 4 のみがキュー内にまだ訪問されていない状態で残っているため、ノード 4 が最後に訪問されます。

この時点で、この無向グラフの幅優先走査が完了しました。

BFS アルゴリズムの擬似コード

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
remove the head u of Q 
mark and enqueue all (unvisited) neighbours of u

BFS アルゴリズムを実装するための Python コード

import collections
def bfs(graph, root):
    visited, queue = set(), collections.deque([root])
    visited.add(root)

while queue:
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")

        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
    print("Following is Breadth First Traversal: ")
    bfs(graph, 0)

以上がBFS アルゴリズムの原理の詳細な分析、図解付きの説明、および BFS アルゴリズムを実装するための Python コード。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。