アルゴリズム・データ構造 プログラミング

[アルゴリズム(Ruby)]深さ優先探索・幅優先探索の解説

アルゴリズム解説_dfs-bfs

こんにちは!じゃいごテックのあつしです。

今回は木構造やグラフの探索に用いられる、深さ優先探索(Depth First Search)と、幅優先探索(Breadth First Search)をご紹介します。

アルゴリズムはほぼ同じですが、データ構造にスタック(stack)を使うと深さ優先探索キュー(queue)を使うと幅優先探索になります。
どちらも全ての要素を探索(全探索)できますが、計算量やメモリ消費を少なくするためには問題に応じて使い分ける必要があります。

最強アルゴリズマー養成講座(通称チーター本)によると下記のような使い分けをすると良いとのことです。

  • 深さ優先探索
    • 全通りを列挙し、結果をまとめる場合
    • 辞書順で最初の解を求める場合
  • 幅優先探索
    • 最短経路を求める場合
    • ある程度近くに求めたい解があることがわかっている場合

深さ優先探索(Depth First Search)

探索開始地点から隣接するノードの突き当りまで探索を行った後、ノードを戻って分岐点があれば分岐点以下の探索を繰り返します。深さ優先探索にはさらに「行きがけ順」「通りがけ順」「帰りがけ順」の探索方法がありますが、今回は「行きがけ順の深さ優先探索」を扱います。

実装例

下図の木構造の [0] から深さ優先探索を行い、 [8] にあるお宝を探索する様子をシミュレーションしてみます。

データ構造

深さ優先探索

サンプルコード
# スタート位置の設定
start = 0
# お宝の位置の設定 (treasure ≠ start)
treasure = 8

# 要素の繋がり設定
tree = [[1],        # [0] は [1]       と隣接
        [0, 2, 4],  # [1] は [0, 2, 4] と隣接
        [1, 3],     # [2] は [1, 3]    と隣接
        [2],        # [3] は [2]       と隣接
        [1, 6],     # [4] は [1, 6]    と隣接
        [6, 8],     # [5] は [6, 8]    と隣接
        [4, 5, 7],  # [6] は [4, 5, 7] と隣接
        [6, 9],     # [7] は [6, 9]    と隣接
        [5],        # [8] は [5]       と隣接
        [7]]        # [9] は [7]       と隣接

# 探索済みチェック用
searched = Array.new(tree.length, false)

# スタート位置の設定
searched[start] = true
stack = tree[start]
step = 0

# 深さ優先探索
while stack.length > 0
  step += 1

  puts <<~"EOS"
         --------------------
         #{step}
         探索候補 -> #{stack}
       EOS

  # 配列末尾から要素を取り出す
  node = stack.pop
  searched[node] = true
  msg = "tree[#{node}] を探索 -> "

  if node == treasure
    puts msg << "お宝発見!"
    # break
  else
    puts msg << "お宝はありませんでした"
  end
  puts "探索済みリスト -> #{searched}"

  # 隣接ノードのうち未探索を探索候補に入れる
  next_nodes = tree[node].select { |node| not searched[node] }
  puts "追加候補 -> #{next_nodes}"
  next_nodes.each { |node| stack.push(node) }
end

処理の流れ

繰り返し処理に入る前にスタート位置 (0) の設定を行います。
(start ≠ treasure とします)

dfs図01

  1. searched[0]true にします。
    (node[0] を探索済みにします。)
  2. tree[0](node[0]の隣接ノード)を先頭から全て stackpush します。
    (初回なのでnode[0]の隣接ノードは未探索です。)

ここから繰り返し処理です。stack が空になるまで繰り返します。

1回目の探索

dfs図02


dfs図03

  1. stack から pop して node に代入します。(node = 1)
  2. searched[1]true にします。
  3. node (1) == treasure (8) -> false でした。
  4. tree[1] を 参照します。
  5. tree[1]: [0, 2, 4] のうち、未探索の [2, 4] を stackpush します。

2回目の探索

dfs図04


dfs図05

  1. stack から pop して node に代入します。(node = 4)
  2. searched[4]true にします。
  3. node (4) == treasure (8) -> false でした。
  4. tree[4] を 参照します。
  5. tree[4]: [1, 6] のうち、未探索の [6] を stackpush します。

3回目の探索

dfs図06


dfs図07

  1. stack から pop して node に代入します。(node = 6)
  2. searched[6]true にします。
  3. node (6) == treasure (8) -> false でした。
  4. tree[6] を 参照します。
  5. tree[6]: [4, 5, 7] のうち、未探索の [5, 7] を stackpush します。

4回目の探索

dfs図08


dfs図09

  1. stack から pop して node に代入します。(node = 7)
  2. searched[7]true にします。
  3. node (7) == treasure (8) -> false でした。
  4. tree[7] を 参照します。
  5. tree[7]: [6, 9] のうち、未探索の [9] を stackpush します。

5回目の探索

dfs図10


dfs図11

  1. stack から pop して node に代入します。(node = 9)
  2. searched[9]true にします。
  3. node (9) == treasure (8) -> false でした。
  4. tree[9] を 参照します。
  5. tree[9]: [7] のうち、未探索はありませんでした。
    (行き止まりまで探索しました。)

6回目の探索

dfs図12


dfs図13

  1. stack から pop して node に代入します。(node = 5)
  2. searched[5]true にします。
  3. node (5) == treasure (8) -> false でした。
  4. tree[5] を 参照します。
  5. tree[5]: [6, 8] のうち、未探索の [8] を stackpush します。

7回目の探索

dfs図14


dfs図15

  1. stack から pop して node に代入します。(node = 8)
  2. searched[8]true にします。
  3. node (8) == treasure (8) -> true でした。(お宝発見!)
  4. tree[8] を 参照します。
  5. tree[8]: [5] のうち、未探索はありませんでした。
    (行き止まりまで探索しました。)

8回目の探索

dfs図16


dfs図17

  1. stack から pop して node に代入します。(node = 2)
  2. searched[2]true にします。
  3. node (2) == treasure (8) -> false でした。
  4. tree[2] を 参照します。
  5. tree[2]: [3] のうち、未探索の [3] を stackpush します。

9回目の探索

dfs図18


dfs図19

  1. stack から pop して node に代入します。(node = 3)
  2. searched[3]true にします。
  3. node (3) == treasure (8) -> false でした。
  4. tree[3] を 参照します。
  5. tree[3]: [2] のうち、未探索はありませんでした。
    (行き止まりまで探索しました。)


    stack が空になったので繰り返し処理を終了します。


幅優先探索(Breadth First Search)

探索開始地点から隣接するノードを探索し、同じ深さのノードの探索が終わってから次の深さの探索を繰り返します。

実装例

下図の木構造の [0] から幅優先探索を行い、 [8] にあるお宝を探索する様子をシミュレーションしてみます。

データ構造

幅優先探索

サンプルコード
# スタート位置の設定
start = 0
# お宝の位置の設定 (treasure ≠ start)
treasure = 8

# 要素の繋がり設定
tree = [[1],        # [0] は [1]       と隣接 
        [0, 2, 4],  # [1] は [0, 2, 4] と隣接
        [1, 3],     # [2] は [1, 3]    と隣接
        [2],        # [3] は [2]       と隣接
        [1, 6],     # [4] は [1, 6]    と隣接
        [6, 8],     # [5] は [6, 8]    と隣接
        [4, 5, 7],  # [6] は [4, 5, 7] と隣接
        [6, 9],     # [7] は [6, 9]    と隣接
        [5],        # [8] は [5]       と隣接
        [7]]        # [9] は [7]       と隣接

# 探索済みチェック用
searched = Array.new(tree.length, false)

# スタート位置の設定
searched[start] = true
queue = tree[start]
step = 0

# 幅優先探索
while queue.length > 0
  step += 1

  puts <<~"EOS"
         --------------------
         #{step}
         探索候補 -> #{queue}
       EOS

  # 配列先頭から要素を取り出す
  node = queue.shift
  searched[node] = true
  msg = "tree[#{node}] を探索 -> "

  if node == treasure
    puts msg << "お宝発見!"
    # break
  else
    puts msg << "お宝はありませんでした"
  end
  puts "探索済みリスト -> #{searched}"

  # 隣接ノードのうち未探索を探索候補に入れる
  next_nodes = tree[node].select { |node| not searched[node] }
  puts "追加候補 -> #{next_nodes}"
  next_nodes.each { |node| queue.push(node) }
end

処理の流れ

繰り返し処理に入る前にスタート位置 (0) の設定を行います。
(start ≠ treasure とします)

bfs図01

  1. searched[0]true にします。
    (node[0] を探索済みにします。)
  2. tree[0](node[0]の隣接ノード)を先頭から全て queueenqueue します。
    (初回なのでnode[0]の隣接ノードは未探索です。)

ここから繰り返し処理です。queue が空になるまで繰り返します。

1回目の探索

bfs図02


bfs図03

  1. queue から dequeue して node に代入します。(node = 1)
  2. searched[1]true にします。
  3. node (1) == treasure (8) -> false でした。
  4. tree[1] を 参照します。
  5. tree[1]: [0, 2, 4] のうち、未探索の [2, 4]queueenqueue します。

2回目の探索

bfs図04


bfs図05

  1. queue から dequeue して node に代入します。(node = 2)
  2. searched[2]true にします。
  3. node (2) == treasure (8) -> false でした。
  4. tree[2] を 参照します。
  5. tree[2]: [1, 3] のうち、未探索の [3]queueenqueue します。

3回目の探索

bfs図06


bfs図07

  1. queue から dequeue して node に代入します。(node = 4)
  2. searched[4]true にします。
  3. node (4) == treasure (8) -> false でした。
  4. tree[4] を 参照します。
  5. tree[4]: [1, 6] のうち、未探索の [6]queueenqueue します。

4回目の探索

bfs図08


bfs図09

  1. queue から dequeue して node に代入します。(node = 3)
  2. searched[3]true にします。
  3. node (3) == treasure (8) -> false でした。
  4. tree[3] を 参照します。
  5. tree[3]: [2] のうち、未探索はありませんでした。
    (行き止まりまで探索しました。)

5回目の探索

bfs図10


bfs図11

  1. queue から dequeue して node に代入します。(node = 6)
  2. searched[6]true にします。
  3. node (6) == treasure (8) -> false でした。
  4. tree[6] を 参照します。
  5. tree[6]: [4, 5, 7] のうち、未探索の [5, 7]queueenqueue します。

6回目の探索

bfs図12


bfs図13

  1. queue から dequeue して node に代入します。(node = 5)
  2. searched[5]true にします。
  3. node (5) == treasure (8) -> false でした。
  4. tree[5] を 参照します。
  5. tree[5]: [6, 8] のうち、未探索の [8]queueenqueue します。

7回目の探索

bfs図14


bfs図15

  1. queue から dequeue して node に代入します。(node = 7)
  2. searched[7]true にします。
  3. node (7) == treasure (8) -> false でした。
  4. tree[7] を 参照します。
  5. tree[7]: [6, 9] のうち、未探索の [9]queueenqueue します。

8回目の探索

bfs図16


bfs図17

  1. queue から dequeue して node に代入します。(node = 8)
  2. searched[8]true にします。
  3. node (8) == treasure (8) -> true でした。(お宝発見!)
  4. tree[8] を 参照します。
  5. tree[8]: [5] のうち、未探索はありませんでした。
    (行き止まりまで探索しました。)

9回目の探索

bfs図18


bfs図19

  1. queue から dequeue して node に代入します。(node = 9)
  2. searched[9]true にします。
  3. node (9) == treasure (8) -> false でした。
  4. tree[9] を 参照します。
  5. tree[9]: [7] のうち、未探索はありませんでした。
    (行き止まりまで探索しました。)


    queue が空になったので繰り返し処理を終了します。


今回のまとめ

  • 深さ優先探索(Depth First Search)幅優先探索(Breadth First Search)全探索の一種です。
  • スタックを使うと深さ優先探索キューを使うと幅優先探索が実装出来ます。
  • 深さ優先探索は一つの分岐を調べ終わってから次の分岐を探索します。
  • 幅優先探索は開始位置から近い順に探索します。
  • 良い実装をするためには探索対象によってアルゴリズムを選択する必要があります。

深さ優先探索・幅優先探索を覚えると競プロの色々な問題が解けるようになります。
paiza練習問題集にも深さ優先探索・幅優先探索メニューがありますので、ぜひ挑戦してみて下さい!

おすすめアウトプット【広告】


paizaに無料登録して動画教材(一部有料)や、練習問題・スキルチェック問題を解いてさらにレベルアップしましょう!
また、あなたのプログラミングスキルが数値化され、(希望があれば)企業からのオファーが届くので、理解度確認&転職活動にオススメです!


スキルテストで自分の市場価値がわかる【paiza】



Ruby学習でお世話になった本




【PR】アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。






通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。







通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。







通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者~中級者向けに書かれているので解説が非常に丁寧です。







Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


-アルゴリズム・データ構造, プログラミング
-, , , ,

© 2024 じゃいごテック