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

7990 ワード
python tree algorithm テキストリンク

グラフィックの参照

  • 頂点から順にすべての頂点
    • にアクセスする.

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

  • 最初に開始点に近い頂点にアクセスし、後に遠い頂点にアクセスする巡回方法
  • 深く探索する前に,まず広範囲の探索を行う.
  • この方法
    • は、2つのノード間で最短経路または任意の経路を探す場合に選択する.

    BFSの利点

  • ノード数が少なく、奥行きが浅い場合に素早く動作します.
  • 単純探索速度は深さ優先探索(DFS)よりも速い.
  • 幅は、複数の経路が最短であっても優先的に探索される.
  • 最短経路が存在する場合、どの経路が無限に深くなっても、必ず最短経路を見つけることができます.

    • BFSの欠点

  • を使用して再帰的に呼び出されるDFSとは異なり、キューは次のナビゲートする頂点を格納する必要があるため、大きなストレージスペースが必要です.
  • ノード数の増加に伴い,探索が必要なノードも増加するのは現実的ではない.

    • BFSの実装

    graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
    def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited
    print(bfs(graph, 'A'))

~~>
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']
    start node Aは、bfs関数を最初に追加し、need_visitに追加した.nodeはAを含み、最初のvisitedはAを持たないので、need_visitでは図['A']の値が拡張される.(-> ['B', 'C'] )
    この過程はずっと繰り返される.

    時間の複雑さ

  • ノード数:V
  • 幹線数:E
    • 隣接リストで表示されている図形(上記のように)
  • O(V+E)O(V + E)O(V+E)
    • 隣接マトリクスパターン
  • O(V2)O(V^2)O(V2)
    • [Spring] Around Advice
    『HyperLedger Fabric実戦』——四、Fabric Solo単機マルチノード配置