幅優先ナビゲーション(BFS:Breath First Search)

977 ワード
幅優先ナビゲーション プログラミング BFS データ構造 アルゴリズム#アルゴリズム# コーディングテスト テキストリンク

幅優先ナビゲーション(BFS)とは?


アルゴリズムは、
  • のあるノードの中で最も隣接する別のノードから順にグラフを参照する.
  • は最も近いノードから最も遠いノードにアクセスするため,広範な探索を行う.(そこでまず「幅」を参照)
  • Queueに隣接ノードを加え、順次DeQueueを行う.
    • 主に
  • の2つのノードの最短パスまたは任意のパスを探すために使用されます.
    • 次にグラフィックを位置決めします.

    幅優先ナビゲーション(BFS)の特徴


    探索速度は
  • 深さ優先探索(DFS)より速かった.
  • すべてのノードをナビゲートする必要があるため、多くのノードを持つグラフでは効率が悪い.
  • 再帰は使用されません.(深さ優先検索は再帰を使用します.)

    • 幅優先ナビゲーション(BFS)の動作原理


    出典:ウィキペディア

    コード実装

    from collections import deque

def BFS (graph, start_node) :
    visited = list()
    queue = deque()
    
    queue.append(start_node)
    
    while queue :
        node = queue.pop()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return visited
    Xtrabackupインクリメンタルバックアップ探索(続き)
    [アルゴリズム]動的プログラミング