素振りの記：深さ優先探索（DFS） N度目入門

はじめに

みんな、えらい！ nikkieです。

今回は苦手意識のある分野に取り組みます。
私、えらいぞ！

なんとなく苦手意識

実は競技プログラミング（AtCoderのABC）を1桁回数やったことがあります。
A・B問題は解けるのですが、C問題から先が難しかったです。
これは競技プログラミングの基本を身につけていないからだろうなと考えていました。
その1つがグラフの探索です。

グラフの探索アルゴリズムはいくつかあると思いますが、1つは深さ優先探索。
AtCoderの解説でDFSという用語が出てきたことが印象に残っています（depth-first search）。

学生時代に学んだ気はするのですが、「再帰」という概念に苦手意識があり、DFSを自分のものにできていない感覚でした。
必要に迫られて今回の素振りです。

『問題解決力を鍛える！アルゴリズムとデータ構造』

積ん読から手に取りました。
13章がグラフ探索です。
「13.3 再帰関数を用いる深さ優先探索」が今の私にはドンピシャでした。

C++の実装例

Pythonで写経：再帰を使ったDFS

以下のグラフを深さ優先探索します。

graph LR
  0-->5
  1-->6
  1-->3
  2-->7
  2-->5
  3-->7
  3-->0
  4-->1
  4-->6
  4-->2
  6-->7
  7-->0

8頂点（番号0〜7）、12辺
graphはリストのリスト
- graph[0]の[5]は、頂点0から頂点5への辺があることを示す
- graph[1]の[6, 3]は、頂点1から頂点6、頂点3への2つの辺があることを示す
各頂点が訪問済みかを表す配列seen
- 訪問済みならスキップ（再度処理しない）
dfs関数（再帰関数）で頂点iの処理
- 頂点iを訪問済みにする
- 頂点iから辿れる頂点について
  - 1つ1つ処理
  - 訪問済みでなければdfsを再帰呼び出し
ノードを1回ずつたどるようにfor文でrangeを回している

実行結果

% hatch run python script.py  # Python 3.12.0 で実行されました
main: Visiting node 0
dfs: Visiting node 0
dfs: Visiting node 5
main: Visiting node 1
dfs: Visiting node 1
dfs: Visiting node 6
dfs: Visiting node 7
dfs: Visiting node 3
main: Visiting node 2
dfs: Visiting node 2
main: Visiting node 3
main: Visiting node 4
dfs: Visiting node 4
main: Visiting node 5
main: Visiting node 6
main: Visiting node 7

頂点0から始める（0, 1, 2, ...）
- 頂点0から頂点5に辿れる
  - 頂点5についてdfs
    - 頂点5は終端
次は頂点1
- 頂点1から頂点6, 3に辿れる
  - 頂点6から頂点7に辿れる
    - 頂点7から頂点0に辿れるが、0は訪問済み
  - 頂点3から頂点7, 0に辿れる
    - いずれも訪問済み
次は頂点2
以下省略

終わりに

苦手意識のあった、再帰を使った深さ優先探索に向き合いました。
今回が何度目になるかは分かりませんが、初見時よりも隣接リスト表現や再帰に驚かずに済み、C++のサンプルコードをPythonで書き換えるまでできました（これが年の功）。
食わず嫌いしていた食材を意を決して食べてみたら、食べられないこと全然なかったという感じです

nikkie-ftnextの日記

イベントレポートや読書メモを発信