［アルゴリズム］BFS(幅優先ナビゲーション)

🧐 BFSとは?

Breadth First Search

の幅を優先するナビゲーションを実行するナビゲーションアルゴリズム

.
最短経路

を探し、最短経路を保証する必要がある場合には

をよく使用する.

準備:キュー(FIFO)

🎈 BFSメソッド

BFSは以下の簡単なアルゴリズムに従って動作する.

キューからノードを取り出します.

は、ノードに接続されているノードにアクセスし、キューを順次挿入する.

最初のノード(1)をキューに挿入します.(赤で表示されているノードはアクセスされているノードです)

ノード(2)とノード(3)にアクセスしたことがないので,キューに入れる.

キューから2を取り出すと、隣接するノード(1)、(3)、(4)、(5)のうち(1)、(3)が既にアクセスしているので、(4)、(5)をスキップし、(4)、(5)をキューに挿入します.

ノード(3)をキューから取り出し、隣接ノード(6)および(7)を挿入します.すべてのノードがアクセス処理されました.残りのノードをキューから取り出すだけです.

(1)から,近接するノードからナビゲーションを開始することを幅優先ナビゲーション(BFS)と呼ぶ.

🎈 BFSコード（Python）

# 방향이 있는 유향그래프
graph_list = {1: set([3, 4]),
	2: set([3, 4, 5]),
    3: set([1, 5]),
    4: set([1]),
    5: set([2, 6]),
    6: set([3, 5])}
    
 
root_node = 1

# BFS
from collections import deque

def BFS_with_adj_list(graph, root):
	visited = []
    queue = deque([root])
    
    while queue:
    	n = queue.popleft()
        if n not in visited:
        	visited.append(n)
            queue += graph[n] - set(visited)
    return visited

print(BFS_with_list(graph_list, root_node))

以上は、https://blog.naver.com/ndb796/221230944971を参照して作成したものです.
画像注記:WikimediaCommons