Пошук у ширину (BFS)

Структури даних і алгоритми в Python

Miriam Antona

Software engineer

Пошук у ширину — бінарні дерева

  • Починається з кореня
  • Відвідує всі вузли кожного рівня

Графічне зображення пошуку в ширину на бінарному дереві пошуку.

Структури даних і алгоритми в Python

Пошук у ширину — бінарні дерева

  def bfs(self):

    if self.root:

      visited_nodes = []

      bfs_queue = queue.SimpleQueue()

Графічне зображення бінарного дерева пошуку.

  • visited_nodes:
  • bfs_queue:
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в 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
Структури даних і алгоритми в Python

Пошук у ширину — графи

  • Графи можуть містити цикли
    • Потрібно перевіряти, чи вершини вже відвідані
Структури даних і алгоритми в 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$ -> кількість ребер
Структури даних і алгоритми в Python

Пошук у ширину — графи

Графічне зображення пошуку в ширину на графі.

Структури даних і алгоритми в Python

BFS vs DFS

BFS

  • Ціль поблизу від початкової вершини
  • Застосування:
    • Вебсканування
    • Пошук найкоротшого шляху в невагових графах
    • Пошук зв'язаних локацій за GPS
    • Як частина складніших алгоритмів

DFS

  • Ціль далеко від початкової вершини
  • Застосування:
    • Розв'язання головоломок з одним розв'язком (напр., лабіринти)
    • Виявлення циклів у графах
    • Пошук найкоротшого шляху у зваженому графі
    • Як частина складніших алгоритмів
Структури даних і алгоритми в Python

Давайте потренуємось!

Структури даних і алгоритми в Python

Preparing Video For Download...