幅優先探索（BFS）
グラフや木構造を幅優先で探索する基本的なアルゴリズム
実行設定
グラフ設定
推奨グラフ
可視化
アルゴリズム実行 - ステップ 1 / 0
操作: 待機中
実行準備中...
配列の状態
500ms
凡例
比較中
発見
探索範囲
探索済み
コード例
TypeScript実装
// 幅優先探索（BFS）の実装
function breadthFirstSearch(graph: Record<string, string[]>, start: string, target?: string): string[] {
const visited = new Set<string>();
const queue: string[] = [start];
const path: string[] = [];
while (queue.length > 0) {
const node = queue.shift()!;
if (visited.has(node)) continue;
visited.add(node);
path.push(node);
// 目標ノードに到達した場合
if (target && node === target) {
break;
}
// 隣接ノードをキューに追加
const neighbors = graph[node] || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
queue.push(neighbor);
}
}
}
return path;
}レベル別BFS実装
// レベル（深さ）を記録するBFS
function bfsWithLevels(graph: Record<string, string[]>, start: string): Map<string, number> {
const visited = new Set<string>();
const queue: [string, number][] = [[start, 0]];
const levels = new Map<string, number>();
while (queue.length > 0) {
const [node, level] = queue.shift()!;
if (visited.has(node)) continue;
visited.add(node);
levels.set(node, level);
// 隣接ノードを次のレベルとしてキューに追加
const neighbors = graph[node] || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
queue.push([neighbor, level + 1]);
}
}
}
return levels;
}DFSとBFSの比較
| 特徴 | BFS（幅優先探索） | DFS（深さ優先探索） |
|---|---|---|
| データ構造 | キュー（FIFO） | スタック（LIFO）または再帰 |
| 探索順序 | レベルごとに探索 | 可能な限り深く探索 |
| 最短経路 | 保証される（無重みグラフ） | 保証されない |
| 空間計算量 | O(|V|) | O(h) ※hは最大深さ |
| 適用例 | 最短経路、レベル順走査 | 経路探索、トポロジカルソート |
BFSの応用例
1. 最短経路問題
無重みグラフにおいて、始点から各頂点への最短経路を求める。迷路の最短経路探索などに使用。
2. ソーシャルネットワーク分析
友達の友達など、特定の距離にいる人々を見つける。LinkedInの「つながり」機能など。
3. Webクローラー
ウェブサイトのリンクを幅優先で探索し、効率的にページを収集。
4. ゲームAI
チェスや将棋などのゲームで、可能な手を探索する際に使用。