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

演習

グラフに対するDFSの実装

この演習では、グラフを走査する depth first search アルゴリズムを実装します。

手順を思い出しましょう。

  1. 任意の頂点から開始する
  2. その頂点を訪問済みリストに追加する
  3. 現在のノードに隣接する各頂点について
    • 訪問済みであれば -> 無視する
    • 未訪問であれば -> 再帰的にDFSを実行する

コードのテストを助けるため、次のグラフが辞書で読み込まれています。

Graphical representation of a graph.

graph = {
  '0' : ['1','2'],
  '1' : ['0', '2', '3'],
  '2' : ['0', '1', '4'],
  '3' : ['1', '4'],
  '4' : ['2', '3']
}

指示

100 XP
  • current_vertex がまだ訪問されていないかを確認します。
  • current_vertex を visited_vertices に追加します。
  • 適切な値を渡して dfs() を再帰的に呼び出します。