BFSとDFS：グラフ探索アルゴリズム

BFS（幅優先探索）

from collections import deque

def bfs(graph, start, goal):
    visited = set()
    queue = deque([start])
    visited.add(start)
    parent = {start: None}
    
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return list(reversed(path))
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)
    return None

DFS（深さ優先探索）

def dfs(graph, start, goal):
    visited = set()
    stack = [start]
    parent = {start: None}
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            if node == goal:
                path = []
                while node is not None:
                    path.append(node)
                    node = parent[node]
                return list(reversed(path))
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    parent[neighbor] = node
                    stack.append(neighbor)
    return None

🔥 Vibe プロンプト

「Randomized DFSで10x10迷路を生成し、BFSで解決。経路とステップ数を表示。」

よくある問題と解決策

| 問題 | 原因 | 解決方法 | |------|------|---------| | 期待通りの結果が出ない | パラメータ設定ミス | デフォルト値と境界条件を確認 | | 実行が遅い | アルゴリズムの効率 | より効率的なデータ構造を使用 | | メモリ不足 | データ量過多 | バッチ処理を検討 | | デバッグが困難 | ログ不足 | 詳細なログ出力を追加 |

さらに学ぶには

• 公式ドキュメントを読む
• GitHubのオープンソース例を参照
• コミュニティディスカッションに参加
• コードを修正して結果の変化を観察

パフォーマンスの考慮事項

大規模データセットや複雑な計算を扱う場合:

1. 時間計算量: Big Oを分析して最適化
2. 空間計算量: メモリと速度のバランス
3. キャッシング: 計算結果を保存して再計算を回避
4. 並列処理: 独立したタスクのマルチスレッド化
5. プロファイリング: 最適化前に計測

実世界での応用

この概念は以下で広く使われています:

• Web開発（ルーティング、認証）
• データサイエンス（特徴量エンジニアリング）
• ゲーム開発（経路探索、物理演算）
• モバイルアプリ（状態管理、キャッシュ）

主要アルゴリズム概要

| アルゴリズム | 時間計算量 | 空間計算量 | 使用例 | |-------------|-----------|-----------|--------| | ダイクストラ | O((V+E)logV) | O(V) | 最短経路 | | A* | O(E) | O(V) | ヒューリスティック経路探索 | | BFS | O(V+E) | O(V) | 重みなし最短経路 | | DFS | O(V+E) | O(V) | トポロジカルソート |

適切なアルゴリズムの選択

1. 重みなしグラフ → BFS
2. 重み付き、非負 → ダイクストラ
3. ヒューリスティックあり → A*
4. 全ペア → フロイド-ワーシャル