1. 学ぶ
    2. /
  2. コース
    3. /
  3. Pythonで学ぶデータ構造とアルゴリズム
Connected

演習

BFS でグラフの頂点を見つける

この演習では、グラフ内で指定した頂点を探索するために、BFS アルゴリズムを改良します。

コードの動作確認に使えるよう、次のグラフが辞書で読み込まれています。

Graphical representation of a graph.

graph = {
  '4' : ['6','7'],
  '6' : ['4', '7', '8'],
  '7' : ['4', '6', '9'],
  '8' : ['6', '9'],
  '9' : ['7', '8']
}

指示

100 XP
  • 探索値を見つけたかどうかを確認します。
  • 見つかった場合は True を返します。
  • for ループ内で、隣接頂点が訪問済みかどうかを確認します。
  • 見つからなかった場合は False を返します。