廣度優先搜尋（BFS）

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

廣度優先搜尋－二元樹

  • 從根節點開始
  • 逐層拜訪所有節點

二元搜尋樹上廣度優先搜尋的圖示。

Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):

    if self.root:

      visited_nodes = []

      bfs_queue = queue.SimpleQueue()

二元搜尋樹的圖示。

  • visited_nodes：
  • bfs_queue：
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)

      while not bfs_queue.empty():

二元搜尋樹的圖示。

  • visited_nodes：
  • bfs_queue：65
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()

二元搜尋樹的圖示。

  • visited_nodes：
  • bfs_queue：
  • current_node：65
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):

    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)

        if current_node.left:

二元搜尋樹的圖示。

  • visited_nodes：65
  • bfs_queue：
  • current_node：65
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):

    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)

二元搜尋樹的圖示。

  • visited_nodes：65
  • bfs_queue：20
  • current_node：65
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65
  • bfs_queue：20、70
  • current_node：65
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65
  • bfs_queue：70
  • current_node：20
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20
  • bfs_queue：70
  • current_node：20
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20
  • bfs_queue：70、10
  • current_node：20
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20
  • bfs_queue：70、10、22
  • current_node：20
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20
  • bfs_queue：10、22
  • current_node：70
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20、70
  • bfs_queue：10、22
  • current_node：70
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20、70
  • bfs_queue：10、22、68
  • current_node：70
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20、70
  • bfs_queue：10、22、68、75
  • current_node：70
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20、70、10
  • bfs_queue：22、68、75
  • current_node：10
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20、70、10
  • bfs_queue：68、75
  • current_node：22
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20、70、10、22
  • bfs_queue：68、75
  • current_node：22
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20、70、10、22、68
  • bfs_queue：75
  • current_node：68
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20、70、10、22、68
  • bfs_queue：
  • current_node：75
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

二元搜尋樹的圖示。

  • visited_nodes：65、20、70、10、22、68、75
  • bfs_queue：
  • current_node：75
Data Structures and Algorithms in Python

廣度優先搜尋－二元樹

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)
    return visited_nodes
  • 複雜度：$O(n)$

二元搜尋樹的圖示。

  • visited_nodes：65、20、70、10、22、68、75
  • bfs_queue：
  • current_node：75
Data Structures and Algorithms in Python

廣度優先搜尋－圖形

  • 圖可能有環
    • 需檢查頂點是否已拜訪過
Data Structures and Algorithms in Python

廣度優先搜尋－圖形

def bfs(graph, initial_vertex):

  visited_vertices = []

  bfs_queue = queue.SimpleQueue()

  bfs_queue.put(initial_vertex)

  visited_vertices.append(initial_vertex)

  while not bfs_queue.empty():

    current_vertex = bfs_queue.get()

    for adjacent_vertex in graph[current_vertex]:

      if adjacent_vertex not in visited_vertices:

        visited_vertices.append(adjacent_vertex)

        bfs_queue.put(adjacent_vertex)

  return visited_vertices
  • 複雜度：$O(V+E)$
    • $V$ → 頂點數
    • $E$ → 邊數
Data Structures and Algorithms in Python

廣度優先搜尋－圖形

圖上廣度優先搜尋的圖示。

Data Structures and Algorithms in Python

BFS 與 DFS 比較

BFS

  • 目標在與「起點」相近處
  • 應用：
    • 網頁爬蟲
    • 在無權重圖找最短路徑
    • 用 GPS 找連通位置
    • 作為複雜演算法的組件

DFS

  • 目標在「起點」較遠處
  • 應用：
    • 解唯一解謎題（如迷宮）
    • 偵測圖中的環
    • 在加權圖找最短路徑
    • 作為複雜演算法的組件
Data Structures and Algorithms in Python

一起來練習吧！

Data Structures and Algorithms in Python

Preparing Video For Download...