BFS

BFSは、breadth-First-Searchであり、幅優先ナビゲーションと呼ばれる.
簡単に言えば、これは隣接ノードからナビゲーションを開始するアルゴリズムである.
DFSの動作が、可能な限り遠いノードを最初にブラウズする場合、BFSは逆である.

1.動作方式

BFS実装では、「第1入力第1出力」(First In First Out)を使用するキューリソース構造が慣例である.
アルゴリズムを記述して隣接ノードをキューに繰り返し入れると、最初に入ったノードは自動的に終了し、隣接ノードからナビゲートします.

ナビゲーション開始ノードをキューに挿入し、アクセス処理を行う.

キューからノードを取り出し、そのノードのすべての隣接ノードからアクセスされていないノードをキューに挿入してアクセス処理を行う.

続行できなくなるまで、この手順

2を繰り返します.

2.例

グラフィックとキューがあるとします.キュー内の要素は上から下へです.

開始ノード「1」をキューに挿入し、アクセス処理を行う.

アクセスしたノードはグレーで、キューから取り出し、現在処理されているノードは青です.

キューから「1」を取り出し、アクセス処理のために、アクセスされていないすべての隣接ノード「2」、「3」、および「8」をキューに挿入する.

キューから「2」を取り出し、未アクセスのノード「7」を挿入してアクセス処理を行う.

キューからノード「3」を取り出し、アクセスされていないすべての隣接ノード「4」および「5」をキューに挿入してアクセス処理を行う.

キューはノード「8」を取り出し、アクセスされていない隣接ノードを無視する.

キューからノード「7」を取り出し、未アクセスの隣接ノード「6」をキューに挿入してアクセス処理を行う.

残りのノードには、アクセスされていない隣接ノードはありません.したがって、すべてのノードを順番に取り出すと、最終的な結果は次のようになります.

したがって、ナビゲーションの順序(キューに入る順序)は次のようになります.1->2->3->8->7->4->5->6.
幅優先ナビゲーションアルゴリズムBFSはキューリソース構造に基づいているので,非常に簡単に実現できる.
Pythonではdequeライブラリを使用することをお勧めします.ナビゲーションにはO(N)時間がかかります.通常、実際の実行時間はDFSよりも優れている.

3.コード

# queue를 구현하기 위한 deque 라이브러리 사용
from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    # 시작 노드로 deque 선언
    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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# bfs수행(2차원 리스트, 시작 노드, 방문 처리를 확인하기 위한 리스트)
bfs(graph, 1, visited)

4.整理

様々な態様で実施することができるが、最も簡単な方法は、以下の表に示す態様を用いることである.
DFSSBFS動作原理スタックキューの実装方法キュー器として再帰関数を用いる
リファレンス
これは就職のためのコードテストです.
間違った部分にコメントを残したら修正します…!!推測を表す