Breadth First Search (BFS)

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Miriam Antona

Software engineer

Breadth first search - binary trees

เริ่มจาก root
เยี่ยมชมทุก node ในทุก level

ภาพแสดงการทำงานของ breadth first search บน binary search tree

Breadth first search - binary trees

  def bfs(self):

    if self.root:

      visited_nodes = []

      bfs_queue = queue.SimpleQueue()

ภาพแสดงโครงสร้าง binary search tree

visited_nodes:
bfs_queue:

Breadth first search - binary trees

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

      while not bfs_queue.empty():

ภาพแสดงโครงสร้าง binary search tree

visited_nodes:
bfs_queue: 65

Breadth first search - binary trees

  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()

ภาพแสดงโครงสร้าง binary search tree

visited_nodes:
bfs_queue:
current_node: 65

Breadth first search - binary trees

  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:

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65
bfs_queue:
current_node: 65

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65
bfs_queue: 20
current_node: 65

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65
bfs_queue: 20, 70
current_node: 65

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65
bfs_queue: 70
current_node: 20

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20
bfs_queue: 70
current_node: 20

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20
bfs_queue: 70, 10
current_node: 20

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20
bfs_queue: 70, 10, 22
current_node: 20

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20
bfs_queue: 10, 22
current_node: 70

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70
bfs_queue: 10, 22
current_node: 70

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70
bfs_queue: 10, 22, 68
current_node: 70

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70
bfs_queue: 10, 22, 68, 75
current_node: 70

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70, 10
bfs_queue: 22, 68, 75
current_node: 10

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70, 10
bfs_queue: 68, 75
current_node: 22

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70, 10, 22
bfs_queue: 68, 75
current_node: 22

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70, 10, 22, 68
bfs_queue: 75
current_node: 68

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70, 10, 22, 68
bfs_queue:
current_node: 75

Breadth first search - binary trees

  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)

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70, 10, 22, 68, 75
bfs_queue:
current_node: 75

Breadth first search - binary trees

  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)$

ภาพแสดงโครงสร้าง binary search tree

visited_nodes: 65, 20, 70, 10, 22, 68, 75
bfs_queue:
current_node: 75

Breadth first search - graphs

กราฟอาจมีวงจร (cycle)
- ต้องตรวจสอบว่า vertex นั้นถูกเยี่ยมชมแล้วหรือยัง

Breadth first search - graphs

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$ -> จำนวน vertex
- $E$ -> จำนวน edge

Breadth first search - graphs

ภาพแสดงการทำงานของ breadth first search บนกราฟ

BFS vs DFS

BFS

เป้าหมายอยู่ใกล้กับจุดเริ่มต้น
การนำไปใช้:
- Web crawling
- หาเส้นทางสั้นที่สุดในกราฟที่ไม่มีน้ำหนัก
- ค้นหาตำแหน่งที่เชื่อมต่อกันด้วย GPS
- ใช้เป็นส่วนหนึ่งของอัลกอริทึมที่ซับซ้อนกว่า

DFS

เป้าหมายอยู่ไกลจากจุดเริ่มต้น
การนำไปใช้:
- แก้ปริศนาที่มีคำตอบเดียว (เช่น เขาวงกต)
- ตรวจหาวงจรในกราฟ
- หาเส้นทางสั้นที่สุดในกราฟที่มีน้ำหนัก
- ใช้เป็นส่วนหนึ่งของอัลกอริทึมที่ซับซ้อนกว่า

มาฝึกกันเถอะ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python