BFS

BFS(Breadth-First search)

探求アルゴリズムです.図にデータを示す場合、開始ノードから距離の同じノードまで順次ナビゲートするアルゴリズム、すなわち、ナビゲーション幅を優先するアルゴリズム.
コアはキューの使用
インプリメンテーション
1.ナビゲーション開始ノードをキューに挿入してアクセス処理する
2.キューから「スタート」(前)ノードを取り出し、「スタート」ノードと隣接ノードをキューに入れてアクセス処理を行います.
3.2つ目のプロセスを、これ以上実行できなくなるまで繰り返す
流行の理解を助けるウィキペディアgifを添付します.
リンクテキスト
Pythonを使用し、Pythonでlist roqを実現するとlistとなります.pop()演算は時間的に非常に非効率であるため,dequeライブラリを用いてキューを実現した.

import sys
from collections import deque #큐를 사용하기 위한 라이브러리

def bfs(graph, start, visited):
    queue = deque([start])

    visited[start] = True

    while queue:
        v = queue.popleft() #왼쪽부터 뽑음 (왼쪽이 가장 먼저 들어간 정보)
        print(v,end=' ')

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

アクセス処理をチェックするとboolタイプのアクセスが生成される

visited=[False]*11 #노드의 개수 +1개의 bool타입 리스트 생성
				   #방문 여부를 체크하기 위함
graph = [
    [], 
    [2,5,9],
	[1,3,4],
	[2,4],
	[3],
	[1,6,8],
	[5,7],
	[6],
	[5],
	[1,10],
	[9]
]
bfs(graph,1,visited)

これはpythonで添付gifを実装する主な文です.
筆者は2次元リストでグラフィックを実現する.Pythonの場合、ディック社でも実現できます.

1 2 3 4 5 6 7 8 9 10

上記のコードを実行すると、添付のgifを一緒に表示すると、理解に役立ちます.
DFSに続く別のグラフィックブラウズ方式&BFSについて説明した.
Q.最短パスを求める質問は、2つのアルゴリズムのうちどれを使った方が良いかです.
答えはBFSです.深度優先ナビゲーションDFSは、最も深い位置に移動して戻り、開始ノードから最も遠いノードに移動してから戻り、他の位置を参照します.
幅優先ナビゲーションのBFSは、上述したように、開始ノードから同じ距離のノードよりも優先されるため、例えば、距離2の位置が宛先であると仮定すると、BFSは距離3のノードよりも前にすべてのデュアルノードをブラウズする.最短パスは、3人ノードに近づくことなくエクスポートできます.
また,最短経路を求めるマルチアウトアルゴリズムも存在し,これは次回に議論する.