DFS, BFSがわかりづらかったので、いくつかの記事を見て個人的に感じた疑問や 「こういうコード例が欲しい」という要望を踏まえて生成AIに生成してもらった。

生成された内容を検証し、コードを実際に動かして確認したところ、 自分の理解が深まる良い記事になったので、このまま公開することにした。

はじめに

LeetCodeでMedium問題を解いていると、必ず遭遇するのがDFS（深さ優先探索）とBFS（幅優先探索）だ。

「Dは深さ、Bは幅」というのは知っている。でも、なぜスタックとキューを使い分けるのか？その本質を理解している人は意外と少ない。

今回は、入れ子リストの例を使って、DFS/BFSの動作原理とデータ構造の関係を視覚的に解説する。

問題設定：入れ子リストをフラット化する

以下のような入れ子構造のリストがあるとする。

data = [1, [4, 5, [6, 7, 8], 2], 3]

これをフラットな配列にしたい。このとき、「どの順番で要素を取り出すか」がDFS/BFSの違いだ。

ツリー構造として可視化する

入れ子リストは、実はツリー構造として表現できる。

        root
       / | \
      1  []  3
         |
        /|\ \
       4 5 [] 2
           |
          /|\
         6 7 8

この木をどう巡回するかで、DFSとBFSが決まる。

DFS（深さ優先探索）：とにかく深く潜る

動作イメージ

「見つけた枝があれば、まずそこを最後まで探索する」

訪問順序：

1 → [中に入る] → 4 → 5 → [さらに中] → 6 → 7 → 8 
→ [戻る] → 2 → [戻る] → 3

結果：[1, 4, 5, 6, 7, 8, 2, 3]

実装：スタックまたは再帰

再帰版

def dfs_recursive(data):
    result = []
    
    def helper(item):
        if isinstance(item, list):
            for sub in item:
                helper(sub)  # 再帰で潜る
        else:
            result.append(item)
    
    helper(data)
    return result

スタック版

def dfs_stack(data):
    result = []
    stack = [data]
    
    while stack:
        item = stack.pop()  # 後入れ先出し（LIFO）
        
        if isinstance(item, list):
            # reversed()で逆順に追加 → pop()で元の順序を保つ
            # [4, 5]を処理する場合: 5→4の順でpush → 4→5の順でpop
            for sub in reversed(item):
                stack.append(sub)
        else:
            result.append(item)
    
    return result

重要：なぜreversed()が必要か？

スタックは「後入れ先出し」なので、そのまま追加すると逆順になってしまう。

# reversed()なしの場合
stack.append([4, 5, 6])
# → pop()で 6, 5, 4 の順に取り出される（逆順！）

# reversed()ありの場合
stack.append([6, 5, 4])  # 逆順で追加
# → pop()で 4, 5, 6 の順に取り出される（正順！）

なぜスタックなのか？

「深く潜って、戻る」という動きがLIFO（後入れ先出し）だから。

スタックは「最後に入れたものを最初に取り出す」データ構造。DFSの「深さ優先」の動きと完全に一致する。

BFS（幅優先探索）：同じ階層を先に見る

動作イメージ

「同じ深さのノードを全部見てから、次の階層へ進む」

訪問順序：

レベル0: 1, [中身], 3
  → 数値だけ取り出す: 1, 3
レベル1: 4, 5, [中身], 2
  → 数値だけ取り出す: 4, 5, 2
レベル2: 6, 7, 8
  → 数値だけ取り出す: 6, 7, 8

結果：[1, 3, 4, 5, 2, 6, 7, 8]

実装：キュー

from collections import deque

def bfs(data):
    result = []
    queue = deque([data])
    
    while queue:
        item = queue.popleft()  # 先入れ先出し（FIFO）
        
        if isinstance(item, list):
            for sub in item:
                queue.append(sub)
        else:
            result.append(item)
    
    return result

なぜキューなのか？

「同じ階層を順番に処理する」という動きがFIFO（先入れ先出し）だから。

キューは「最初に入れたものを最初に取り出す」データ構造。BFSの「幅優先」の動きと完全に一致する。

二重ループではダメな理由

初学者がやりがちなミス：

# ❌ これは深さ2までしか対応できない
for item in data:
    if isinstance(item, list):
        for sub in item:
            print(sub)

問題点：入れ子の深さが3以上になると対応不可能

data = [1, [2, [3, [4, [5]]]]]

# 二重ループの場合
for item in data:
    if isinstance(item, list):
        for sub in item:
            print(sub)  # 3までしか到達できない

# 三重ループにしても...
for item in data:
    if isinstance(item, list):
        for sub in item:
            if isinstance(sub, list):
                for subsub in sub:
                    print(subsub)  # 4までしか到達できない

深さが不定の場合、ループのネストを事前に決められない。

これが、再帰やスタック/キューといった動的なデータ構造が必要な理由だ。

実際のツリー問題での違い

       1
      / \
     2   3
    / \
   4   5

DFS（深さ優先）

訪問順: 1 → 2 → 4 → 5 → 3
（左の枝を全部探索してから右へ）

BFS（幅優先）

訪問順: 1 → 2 → 3 → 4 → 5
（階層ごとに左から右へ）

まとめ

項目 DFS BFS
データ構造 スタック（再帰） キュー
動作原理 LIFO（後入れ先出し） FIFO（先入れ先出し）
探索方向 深さ優先（縦） 幅優先（横）
用途 経路探索、トポロジカルソート 最短経路、レベル順探索

核心：データ構造の選択が、探索の動きを決定する。

スタックを使えば自動的に深さ優先になり、キューを使えば自動的に幅優先になる。これがDFS/BFSの本質だ。

次にツリーやグラフ問題に出会ったとき、「スタックかキューか」を考えるだけで、解法の方向性が見えてくる。

補足：「listでキューを実装してはいけない」理由

よくある疑問

「キューってlistのpop(0)でも実現できるよね？」

答え：できるが、絶対にやるな。

計算量の罠

# ✓ 動作はする
queue = []
queue.append(1)  # enqueue
item = queue.pop(0)  # dequeue

# しかし...

時間計算量の比較

操作 list deque
append() O(1) O(1)
pop(0) / popleft() O(n) O(1)

なぜO(n)になるのか？

Pythonのlistは内部的に連続配列として実装されている。

list = [A, B, C, D, E]

pop(0)を実行すると：

Before: [A, B, C, D, E]
Step 1: Aを削除
Step 2: B, C, D, E を全て左にシフト ← O(n)
Final:  [B, C, D, E]

要素数nに比例して処理時間が増える。

実際の速度差：キューサイズによる影響

小規模キュー（1,000要素）

N = 1,000,000
QSIZE = 1,000

結果：
list:  0.367秒
deque: 0.264秒
比率：約1.4倍

小規模なキューではPythonの最適化により、差は比較的小さい。

中規模キュー（10,000要素）

N = 1,000,000
QSIZE = 10,000

結果：
list:  2.156秒
deque: 0.233秒
比率：約9.3倍

キューサイズが10倍になると、速度差も約10倍に拡大。

理論的な説明

list.pop(0)の計算量：O(QSIZE)
→ キューサイズに比例して遅くなる

deque.popleft()の計算量：O(1)
→ キューサイズに影響されない

LeetCodeでの実害

Binary Tree Level Order Traversalのような問題では、ツリーのノード数が10,000を超えることは珍しくない。

  • QSIZE = 1,000: 両方ともAC（ただしlistは遅い）
  • QSIZE = 10,000: listでTLE（Time Limit Exceeded）の可能性
  • QSIZE = 100,000: listは確実にTLE

結論：LeetCodeでキューを使う場合、必ずcollections.dequeを使うこと。

「動く」と「効率的」は別物。

キューを実装するときは、必ずcollections.dequeを使うこと。これがアルゴリズム問題を解く上での鉄則だ。

記事の正しい使い分け

# スタック（LIFO）→ list
stack = []
stack.append(1)  # O(1)
stack.pop()      # O(1) ← 末尾から取るので速い

# キュー（FIFO）→ deque
from collections import deque
queue = deque()
queue.append(1)    # O(1)
queue.popleft()    # O(1) ← 先頭から取るのも速い

データ構造の選択ミスは、コードを遅くする最大の要因になる。