深さ優先探索

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software engineer

ツリー／グラフの走査

• すべてのノードを順にチェックするプロセス
• 深さ優先探索
• 幅優先探索

深さ優先探索 - 二分木

• 通りがけ順・中間順（In-order）
• 行きがけ順・先行順（Pre-order）
• 帰りがけ順・後行順（Post-order）

通りがけ順走査

• 順序： 左

通りがけ順走査

• 順序： 左 → 現在

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査

• 順序： 左 → 現在 → 右

通りがけ順走査 - コード

• 順序： 左 → 現在 → 右

def in_order(self, current_node):

  if current_node:

    self.in_order(current_node.left_child)

    print(current_node.data)

    self.in_order(current_node.right_child)


my_tree.in_order(my_tree.root)

10
20
22
65
68
70
75

• 計算量：$O(n)$
  • $n$ → ノード数

行きがけ順走査

• 順序： 現在

行きがけ順走査

• 順序： 現在 → 左

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査

• 順序： 現在 → 左 → 右

行きがけ順走査 - コード

• 順序： ルート → 左 → 右

  def pre_order(self, current_node):
    if current_node:
      print(current_node.data)
      self.pre_order(current_node.left_child)
      self.pre_order(current_node.right_child)

my_tree.pre_order(my_tree.root)

65
20
10
22
70
68
75

• 計算量：$O(n)$
  • $n$ → ノード数

帰りがけ順

• 順序： 左

帰りがけ順

• 順序： 左 → 右

帰りがけ順

• 順序： 左 → 右 → 現在

• 計算量：$O(n)$

  • $n$ → ノード数

通りがけ順・行きがけ順・帰りがけ順の使い分け

• 通りがけ順

  • 二分探索木を使ってノードの値を昇順に取得する

• 行きがけ順

  • ツリーのコピー作成
  • 前置記法の取得

• 帰りがけ順

  • 二分木の削除
  • 後置記法の取得

深さ優先探索 - グラフ

• グラフにはサイクルを持つことがある
  • 訪問済みの頂点を管理する必要がある
• 手順：
  1. ランダムな頂点から開始
  2. 現在の頂点を訪問済み頂点リストに記録
  3. 現在のノードに隣接する各頂点
     • 訪問済みの場合 -> 無視する
     • 訪問されていない場合 -> 再帰的に深さ優先探索を実行

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - コード

def dfs(visited_vertices, graph, current_vertex):
    if current_vertex not in visited_vertices:
        print(current_vertex)
        visited_vertices.add(current_vertex)
        for adjacent_vertex in graph[current_vertex]:
            dfs(visited_vertices, graph, adjacent_vertex)

• 計算量：$O(V+E)$
  • $V$ → 頂点数
  • $E$ → エッジ数

練習しましょう！

Pythonで学ぶデータ構造とアルゴリズム