幅優先探索

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

Miriam Antona

Software engineer

幅優先探索 - 二分木

ルートノードから始まる
すべてのレベルにあるすべてのノードを訪問する

二分探索木に対する幅優先探索の図示。

幅優先探索 - 二分木

  def bfs(self):

    if self.root:

      visited_nodes = []

      bfs_queue = queue.SimpleQueue()

二分探索木の図示。

visited_nodes:
bfs_queue:

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - 二分木

  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

幅優先探索 - グラフ

グラフはサイクルを持つことがある
- 頂点がすでに訪問済みか確認する

幅優先探索 - グラフ

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$ → エッジ数

幅優先探索 - グラフ

グラフ上の幅優先探索の図示。

幅優先探索と深さ優先探索

幅優先探索

ターゲットが開始頂点に近い
用途：
- Webクローリング
- 重みなしグラフで最短経路を見つける
- GPSを使った特定地点からのすべての接続地点の検索
- より高度なアルゴリズムの中のパーツとして使用される

深さ優先探索

ターゲットが開始頂点から離れたところにある
用途：
- 解答が1つしかないパズル（例：迷路）を解く
- グラフ内のサイクルの検出
- 重み付きグラフで最短経路を見つける
- より高度なアルゴリズムの中のパーツとして使用される

練習しましょう！

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