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

1871 ワード
データ構造 アルゴリズム#アルゴリズム# プログラミング 勉強する テキストリンク

🧐 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
    31[小鬼手帳]-POST練習(注釈)
    サービス側プログラミング(十五)-Django-自動化テスト入門