深度優先搜尋（DFS）

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

樹／圖走訪

  • 造訪「所有節點」的流程
  • 深度優先搜尋（DFS）
  • 廣度優先搜尋（BFS）
Data Structures and Algorithms in Python

深度優先搜尋－二元樹

  • 中序（In-order）
  • 先序（Pre-order）
  • 後序（Post-order）
Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left
Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current
Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪

  • 「順序」：Left -> Current -> Right

In-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

中序走訪－實作

  • 「順序」：Left -> Current -> Right
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$ -> 節點數
Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current
Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left
Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪

  • 「順序」：Current -> Left -> Right

Pre-order 走訪二元搜尋樹的圖示。

Data Structures and Algorithms in Python

先序走訪－實作

  • 「順序」：Root -> Left -> Right
  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$ -> 節點數
Data Structures and Algorithms in Python

後序

  • 「順序」：Left
Data Structures and Algorithms in Python

後序

  • 「順序」：Left -> Right
Data Structures and Algorithms in Python

後序

  • 「順序」：Left -> Right -> Current

  • 複雜度：$O(n)$

    • $n$ -> 節點數
Data Structures and Algorithms in Python

何時用中序、先序、後序

  • 「中序（in-order）」

    • 用 BST 取得節點值的遞增序

  • 「先序（pre-order）」

    • 複製樹結構
    • 取得前綴表示式

  • 「後序（post-order）」

    • 刪除二元樹
    • 取得後綴表示式
Data Structures and Algorithms in Python

深度優先搜尋－圖

  • 圖可能有環
    • 需記錄已訪問的頂點
  • 步驟：
    1. 從任一頂點開始
    2. 將目前頂點加入已訪清單
    3. 對每個相鄰頂點
      • 若已訪問 -> 略過
      • 若未訪問 -> 遞迴執行 DFS
Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－圖

在圖上進行深度優先搜尋的圖示。

Data Structures and Algorithms in Python

深度優先搜尋－實作

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$ -> 邊數
Data Structures and Algorithms in Python

一起來練習吧！

Data Structures and Algorithms in Python

Preparing Video For Download...