アルゴ AIに質問関連 2 問題

BFS

幅優先探索

概要

キューを使ってグラフや木を幅（距離）順に探索するアルゴリズム。出発ノードから近い順に訪問するため、最短経路（辺の重みが等しい場合）を保証できる。グリッドの連結成分（島の数など）を列挙するときも有効。時間計算量は頂点数 $V$ と辺数 $E$ の和 $O(V + E)$ 。Python では collections.deque の popleft で $O(1)$ のデキューを実現する。

擬似コード

from collections import deque

def bfs(root):
    if not root:
        return

    queue = deque([root])

    while queue:
        # 階層毎に処理を行いたい場合、len() と for ループを用いる
        # level_length = len(queue)
        # for _ in range(level_length):
        node = queue.popleft()

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Key point

両端キュー（double-ended queue）を作成する。
- deque(...) は、渡した値を「両端から高速に追加・削除できるキュー」に変換する。
- iterable な要素のみ引数に渡すことが可能。

参考

計算量

操作	平均	最悪
探索（グラフ）
探索（グリッド）

#199Binary Tree Right Side ViewMedium✓ 解答済 #200Number of IslandsMedium✓ 解答済

学習メモ

Python の list.pop(0) は $O(n)$ なので必ず collections.deque の popleft() を使う。この一点を意識するだけで TLE を防げる。

BFS

擬似コード

Key point

参考

計算量

関連する問題

学習メモ