幅優先探索をマスターする

はじめに

上長からの幅優先探索の第一引数に渡すデータ作成のリクエストに瞬時に対応することができなかった。

エンジニアとしての実力が可視化された瞬間だった。

スキルアップできる、実力不足を痛感できる環境にいることに感謝して、圧倒的な実力を示していきたい。

手始めに、Pythonで幅優先探索を行おう。

幅優先探索(Breadth-First Search, BFS)とは

グラフやツリー構造の探索アルゴリズムの一つ。

近いノードから順番に広げていく方法。

最短経路を見つけるのに適している。

幅を優先して探索していく。

ソースコードの例

from collections import deque

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

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(f"訪問: {node}")
            visited.add(node)
            queue.extend([neighbor for neighbor in graph[node] if neighbor not in visited])

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')

出力結果

訪問: A
訪問: B
訪問: C
訪問: D
訪問: E
訪問: F

探索の流れ

  1. スタートノードをキューに追加
  2. キューからノードを取り出し、訪問済みにする
  3. そのノードに隣接するノードをキューに追加(まだ訪問していない場合)
  4. キューが空になるまで繰り返す

スタートノードをキューに追加

今回の例のスタートノードは、A。

bfs関数の第二引数に渡ってくる。そして、dequeに渡す。

deque(double-ended queue)は、両端からデータの追加削除ができるcollectionsモジュールに含まれるデータ構造。

キューからノードを取り出し、訪問済みにする

まずは4行目で、訪問済みのノードを格納する空の集合を定義している。

9行目でpopleftメソッドでキューから取り出したノードをnodeに格納している。

9~11行目でvisitedにまだ格納されていないノードを格納している。

10行目の出力結果

最初に格納されている値

そのノードに隣接するノードをキューに追加(まだ訪問していない場合)

queue.extend([neighbor for neighbor in graph[node] if neighbor not in visited])

よくわからなかったので、GPTに相談してみた。

キューが空になるまで繰り返す

訪問: A
訪問: B
訪問: C
訪問: D
訪問: E
訪問: F

ここまで書いてみたが、よくわからない

具体的にみていこう。

グラフとは

これは何を意味するのか?

GPTに聞いてみた。

幅優先探索なので

探索をする。

先ほどの図を探索していくということだろう。

Aスタート

A訪問済み

キューに未訪問の隣接ノードを追加

queue.extend([neighbor for neighbor in graph[node] if neighbor not in visited])

リストオブジェクト生成

neighbor

return

queueに値が入る

while繰り返し

popleft

理解した

ここまでくるとだいぶわかってきた。

ひとつ完全理解すると、他の似たようなことも理解できるようになる。

Fが二つ

Fは二つある。

最初はnodeに追加される。

2回目はvisitedにあるので、弾かれる。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です