🔍

BFSをステップバイステップで実装してみよう

に公開
Python
アルゴリズム
BFS
tech

BFS（幅優先探索）の実装手順まとめ

✅ 目標

BFS（幅優先探索）を**deque（キュー）**構造で実装しながら、
探索の流れとコードの仕組みを体系的に理解する。

📌 ステップごとの解説

【ステップ1】グラフの基本構造を作る

n, m, v = map(int, input().split())
graph = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(n):
    graph[i].sort()
  • 頂点数：n、辺の数：m、開始頂点：v
  • graphは隣接リスト形式
  • 頂点番号が小さい順に訪問するために.sort()を使用

【ステップ2】訪問リストとBFSの枠組みを作る

from collections import deque

visited = [False] * n

def bfs_queue(start):
    queue = deque([start])
    visited[start] = True
  • dequeは高速なキュー操作が可能なデータ構造
  • 開始頂点をキューに追加し、訪問済みにマークする

【ステップ3】BFSのループを実行する

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for neighbor in graph[v]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True
  • キューから頂点を取り出し
  • 隣接していて未訪問の頂点をキューに追加

【ステップ4】BFS関数を実行する

bfs_queue(v)
  • vは開始頂点
  • 探索順が出力される

✅ 入力例

4 4 0
0 1
0 2
1 2
2 3

✅ 出力結果

0 1 2 3

💡 ポイントまとめ

概念 説明
deque 高速なキュー操作のためのデータ構造
popleft() キューの先頭を取り出す（BFSの中核動作）
append() 隣接頂点をキューに追加
visited[] 重複訪問を防ぐためのチェックリスト

🏁 完成版のBFSコード例

from collections import deque

n, m, v = 4, 4, 0
graph = [[] for _ in range(n)]
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]

for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)

for i in range(n):
    graph[i].sort()

visited = [False] * n

def bfs_queue(start):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for neighbor in graph[v]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

bfs_queue(v)

✅ この構造を覚えれば、ほとんどのBFS問題に対応可能！

Discussion