深さ優先探索（DFS）

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

Miriam Antona

Software engineer

木／グラフの走査

• すべてのノードを訪問する手順
• 深さ優先探索（DFS）
• 幅優先探索（BFS）

深さ優先探索 - 二分木

• 中順（in-order）
• 先行順（pre-order）
• 後行順（post-order）

中順走査（in-order）

• 順序: 左

中順走査（in-order）

• 順序: 左 -> 現在

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-order）

• 順序: 左 -> 現在 -> 右

中順走査（in-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$ -> ノード数

先行順走査（pre-order）

• 順序: 現在

先行順走査（pre-order）

• 順序: 現在 -> 左

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査（pre-order）

• 順序: 現在 -> 左 -> 右

先行順走査 - 実装

• 順序: ルート -> 左 -> 右

  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$ -> ノード数

後行順（post-order）

• 順序: 左

後行順（post-order）

• 順序: 左 -> 右

後行順（post-order）

• 順序: 左 -> 右 -> 現在

• 計算量: $O(n)$

  • $n$ -> ノード数

in-order / pre-order / post-order の使い分け

• in-order

  • BSTでノード値を昇順取得

• pre-order

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

• post-order

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

深さ優先探索 - グラフ

• グラフにはサイクルがあり得る
  • 訪問済み頂点の管理が必要
• 手順:
  1. 任意の頂点から開始
  2. 現在の頂点を訪問済みに記録
  3. 現在ノードの隣接頂点ごとに
     • 訪問済みなら無視
     • 未訪問なら再帰的にDFSを実行

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - グラフ

深さ優先探索 - 実装

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$ -> 辺数

¡Vamos a practicar!

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