アルゴリズム - 7. 深さ優先探索（DFS）
深さ優先探索（DFS）を使うタイミング
DFSはすべてのパスを探索する必要がある場合、またはバックトラッキング前に深く探索する必要がある場合に使用します。木の走査で最もよく使用されますが、以下のケースにも適応できます：
- 木の走査（クラシックなユースケース - 中間順、前順、後順）
- 経路探索（ノード間に経路が存在するかのチェック）
- 連結成分（グリッド内の島を見つける）
- サイクル検出（グラフ内のループを検出）
- トポロジカルソート（依存関係の順序付け）
- バックトラッキング問題（順列の生成、パズルの解決）
- バックトラッキング前に各ブランチをできるだけ深く探索する必要がある問題
例題
ファイルシステムの探索：フォルダ構造が与えられたとき、特定の拡張子を持つすべてのファイルを見つけます。ファイルシステムは以下のようになっています：
root/
├── documents/
│ ├── report.pdf
│ └── notes.txt
├── code/
│ ├── main.js
│ └── utils/
│ └── helper.js
└── images/
└── logo.pngシステム内のすべての.jsファイルを見つけてください。
答え：DFSはroot → documents → report.pdf → notes.txt（バックトラック）→ code → main.js（見つかった！）→ utils → helper.js（見つかった！）（バックトラック）→ images → logo.pngと探索します。結果：[main.js, helper.js]
最も重要な洞察
DFSは別のパスを試す前に1つのパスを完全に探索することにコミットします - 各ブランチに再帰的に深く潜り、行き止まりに達したらバックトラックして代替案を探索することで、パスを見逃すことなくすべてのノードを正確に1回ずつ体系的に訪問します。
メンタルノート：このアルゴリズムの天才性は、コールスタックを自然なバックトラッキングメカニズムとして使用することにあります。各ノードで単純に「自分自身を処理してから、子供を完全に探索する」と言うだけです。再帰が行き止まりに達したときに未探索のブランチに戻ることを自動的に処理します。
決定フレームワーク
各ノードで、この単純な順序に従います：
- 現在のノードを処理（いつ、どのように処理するかは走査タイプに依存）
- 子を再帰的に探索（木の場合は左/右、グラフの場合は隣接ノード）
- 再帰にバックトラッキングを任せる（コールスタック経由で自動）
唯一の決定は現在のノードをいつ処理するかです：
- 前順：子を探索する前に処理（ルート → 左 → 右）
- 中間順：子の間で処理（左 → ルート → 右）
- 後順：子を探索した後に処理（左 → 右 → ルート）
各走査タイプをいつ使うか（シンプルな例）
前順（ルート → 左 → 右）
必要な場合：子を処理する前に親ノードを処理または訪問する必要がある場合 - 通常、コピーの作成、階層の印刷、または親が子に必要な情報を含んでいる場合です。
シンプルな例：フォルダ構造のコピー - フォルダを新しい場所にコピーする場合、次の手順が必要です：
- 最初に親フォルダを作成（ルート）
- その後、サブフォルダとファイルをコピー/作成（子）
まだ存在しないフォルダにファイルを置くことはできません！
中間順（左 → ルート → 右）
必要な場合：二分探索木からソートされた順序でデータを取得する必要がある場合、またはノードを自然な順序で処理する必要がある場合 - 左の部分木には小さい値が含まれ、右の部分木には大きい値が含まれます。
シンプルな例：会社の木構造で給与順に全従業員を印刷：
- 左ブランチ = より低い給与の従業員
- 現在のノード = この従業員の給与
- 右ブランチ = より高い給与の従業員
中間順走査により：$50k、$60k、$70k、$80k...ソートアルゴリズムなしで完璧にソートされます！
後順（左 → 右 → ルート）
必要な場合：親を処理する前にすべての子から情報を処理または収集する必要がある場合 - 通常、削除、サイズの計算、または親が子の結果に依存する場合です。
シンプルな例：コンピューター上のフォルダの総サイズの計算：
- まず、サブフォルダA内のすべてのファイルのサイズを取得（左の子）
- 次に、サブフォルダB内のすべてのファイルのサイズを取得（右の子）
- 最後に、それらを合計して親フォルダの総サイズを取得
すべてのコンテンツを測定するまでフォルダの総サイズはわかりません！
コード
フォルダ構造内のファイルの検索
実際の問題を解決するためのDFSを実装しましょう：プロジェクトフォルダを検索してすべてのJavaScriptファイルを見つけます。この例は、DFSが各フォルダブランチを深く探索してから次に移動し、パススタックを使用して現在の位置を追跡し、必要に応じてバックトラックする方法を示しています。
// 実用例：フォルダ構造内の特定のファイルを見つける
// プロジェクト内のすべてのJavaScriptファイルを検索してみましょう
class FileNode {
constructor(name, isFolder = false) {
this.name = name;
this.isFolder = isFolder;
this.children = [];
}
addChild(child) {
this.children.push(child);
return child;
}
}
// メインのDFSアルゴリズム - 特定の拡張子を持つファイルを見つける
function findFilesWithExtension(rootFolder, extension) {
const foundFiles = [];
const pathStack = []; // 完全なファイルパス用の現在のパスを追跡
function searchFolder(node) {
// ベースケース：nullの場合、探索するものはない
if (node == null) {
return;
}
// 現在のアイテムをパスに追加
pathStack.push(node.name);
const currentPath = pathStack.join('/');
// DECISION FRAMEWORK: これが探しているものかチェック
const isTargetFile = !node.isFolder && node.name.endsWith(extension);
if (isTargetFile) {
foundFiles.push(currentPath);
}
// すべての子を再帰的に探索（深く進む！）
for (const child of node.children) {
searchFolder(child); // この子を完全に探索
}
// バックトラック：探索が完了したら現在のパスから削除
pathStack.pop();
}
searchFolder(rootFolder);
return foundFiles;
}
// 例のファイルシステムを構築
const root = new FileNode('project', true);
// JavaScriptファイルを含むsrcフォルダを追加
const src = root.addChild(new FileNode('src', true));
src.addChild(new FileNode('index.js'));
src.addChild(new FileNode('app.js'));
const components = src.addChild(new FileNode('components', true));
components.addChild(new FileNode('Button.js'));
components.addChild(new FileNode('Button.css')); // JSファイルではない
// マークダウンファイルを含むdocsフォルダを追加
const docs = root.addChild(new FileNode('docs', true));
docs.addChild(new FileNode('README.md'));
docs.addChild(new FileNode('guide.md'));
// ルートに設定ファイルを追加
root.addChild(new FileNode('package.json'));
root.addChild(new FileNode('config.js'));
// すべてのJavaScriptファイルを見つける
const jsFiles = findFilesWithExtension(root, '.js');
console.log('JavaScriptファイルが見つかりました：');
console.log(jsFiles);
// 出力：
// [
// 'project/src/index.js',
// 'project/src/app.js',
// 'project/src/components/Button.js',
// 'project/config.js'
// ]
// DFSの動作を確認するために1つのパスをトレースしてみましょう：
// 1. 'project'から開始
// 2. 最初の子'src'へ移動（深く潜る！）
// 3. 'src'の最初の子'index.js'へ移動（さらに深く！）
// 4. 'index.js'には子がないので処理してバックトラック
// 5. 'src'の次の子'app.js'へ移動（兄弟を探索）
// 6. 'app.js'には子がないので処理してバックトラック
// 7. 'src'の次の子'components'へ移動（新しいブランチに潜る）
// ... 以降同様3つの走査順序の視覚化
各走査順序がノードをどのように異なる順番で訪問するかを見るために、シンプルな木を使用しましょう：
A
/ \
B C
/ \
D Eこの木構造では、各走査タイプは親をその子に対していつ処理するかに基づいて、異なるシーケンスでノードを訪問します。
class SimpleNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 前順：子の前にノードを処理（ルート → 左 → 右）
function preOrder(node) {
if (node == null) return [];
const result = [];
function traverse(current) {
if (current == null) return;
// DECISION FRAMEWORK: 現在を最初に処理
result.push(current.value);
traverse(current.left); // その後左へ
traverse(current.right); // その後右へ
}
traverse(node);
return result;
}
// 中間順：子の間でノードを処理（左 → ルート → 右）
function inOrder(node) {
if (node == null) return [];
const result = [];
function traverse(current) {
if (current == null) return;
traverse(current.left); // まず左へ
// DECISION FRAMEWORK: 現在を中間で処理
result.push(current.value);
traverse(current.right); // その後右へ
}
traverse(node);
return result;
}
// 後順：子の後でノードを処理（左 → 右 → ルート）
function postOrder(node) {
if (node == null) return [];
const result = [];
function traverse(current) {
if (current == null) return;
traverse(current.left); // まず左へ
traverse(current.right); // その後右へ
// DECISION FRAMEWORK: 現在を最後に処理
result.push(current.value);
}
traverse(node);
return result;
}
// 例の木を構築
const tree = new SimpleNode('A');
tree.left = new SimpleNode('B');
tree.right = new SimpleNode('C');
tree.left.left = new SimpleNode('D');
tree.left.right = new SimpleNode('E');
console.log('\n走査順序：');
console.log('前順 (ルート-左-右):', preOrder(tree)); // [A, B, D, E, C]
console.log('中間順 (左-ルート-右):', inOrder(tree)); // [D, B, E, A, C]
console.log('後順 (左-右-ルート):', postOrder(tree)); // [D, E, B, C, A]
// 各走査の実世界での意味：
// 前順： 木のコピーを作成（子の前に親を処理）
// 中間順：BSTからソートされた値を取得（左 < ルート < 右）
// 後順： 木を安全に削除（親の前に子を削除）疑問バスター
よくある疑問：「DFSは無限ループにはまったり、ノードを再訪問したりしませんか？サイクルのあるグラフがある場合や、木が実際に巨大な場合はメモリ不足になりませんか？」
なぜDFSが失敗する可能性があると思うか
人々が互いに友達になれる（サイクルを作成する）ソーシャルネットワークの探索を考えてみてください：
Alice → Bob → Charlie
↑ ↓
└─────────────┘心配になるかもしれません：
- 「AliceからBob、そしてCharlie、そしてAliceに戻ると...永遠にスタックしてしまう！」
- 「木が1000レベルの深さだったら？コールスタックがオーバーフローしませんか？」
- 「同じノードを複数回処理しないことをどうやって知ることができますか？」
なぜこの考え方が不完全なのか
重要な気づき：DFSにはこれらの懸念に対する2つの簡単な解決策があります：
- サイクル対策：訪問済みセットを使用して探索済みノードを追跡
- 深さ対策：コールスタック空間はO(高さ)であり、O(ノード数)ではない
サイクルのあるグラフをどのように処理するか見てみましょう：
function dfsGraph(startNode, graph) {
const visited = new Set();
const result = [];
function explore(node) {
// 再訪問を防ぐ - これがサイクルを断ち切る！
if (visited.has(node)) {
return;
}
visited.add(node);
result.push(node);
// 未訪問のすべての隣接ノードを探索
for (const neighbor of graph[node]) {
explore(neighbor);
}
}
explore(startNode);
return result;
}
// サイクルのあるグラフの例
const socialNetwork = {
'Alice': ['Bob', 'Charlie'],
'Bob': ['Charlie'],
'Charlie': ['Alice'] // サイクルを作成！
};
console.log(dfsGraph('Alice', socialNetwork));
// ['Alice', 'Bob', 'Charlie'] - 無限ループなし！具体例：DFSはすべての木の形状を効率的に処理
DFSがロバストである理由を見るために、異なる木の形状をトレースしてみましょう：
極端に深い木（リンクリスト形状）：
1 → 2 → 3 → 4 → ... → 1000- 空間計算量：コールスタック用にO(1000)
- しかし、1000個のノードすべてを正確に1回ずつ訪問
- 現代のシステムは数千の再帰呼び出しを簡単に処理
極端に広い木：
1
/ / | \ \
2 3 4 5 6 (1000個の子)- 空間計算量：O(2) - 現在のパスの深さだけ！
- 子2を完全に探索し、バックトラックし、次に子3、など
- すべての兄弟を同時に保存する必要はない
バランスの取れた木：
1
/ \
2 3
/ \ / \
4 5 6 7- バランスの取れた木の空間計算量：O(log n)
- 再帰的探索の最も効率的なケース
なぜO(log n)？ n個のノードを持つバランスの取れた木では、高さはlog₂(n)です。たとえば、1,000,000個のノードを持つバランスの取れた木の高さは約20レベルだけです。DFSは現在のパスのみをメモリに保持し（すべてのノードではない）、コールスタックは100万ノードでも20フレームを超えることはありません！
数学的証明：空間計算量がO(log n)である理由
バランスの取れた二分木でn個のノードが高さlog₂(n)を持つ理由を段階的に証明しましょう：
ステップ1：バランスの取れた二分木の構造を理解する
- 各レベルiは最大2^i個のノードを持つ（レベル0は1個、レベル1は2個、レベル2は4個など）
- 高さhの完全バランス木は正確に2^(h+1) - 1個のノードを持つ
ステップ2：ノード数(n)と高さ(h)の関係を導出する
高さhのバランスの取れた木：
- 最大ノード数 = 1 + 2 + 4 + 8 + ... + 2^h
- これは等比級数 = 2^(h+1) - 1
したがって：n ≤ 2^(h+1) - 1なぜ n ≤ 2^(h+1) - 1 なのか？ この不等式は高さhの二分木の最大ノード数を表します：
- 各レベルiは最大2^i個のノードを持つことができる
- 総ノード数 = 2^0 + 2^1 + 2^2 + ... + 2^h（すべてのレベルの合計）
- 等比級数の公式を使用：合計 = a(r^n - 1)/(r - 1)、ここでa=1、r=2、n=h+1
- 結果：n = (2^(h+1) - 1)/1 = 2^(h+1) - 1
=（等号）ではなく≤（不等号）を使う理由は、木が最後のレベルで完全に埋まっていない可能性があるからです。例えば、次の2つの高さ2の木はどちらも有効です：
完全な木 (n = 7): 不完全な木 (n = 4):
1 1
/ \ / \
2 3 2 3
/ \ / \ /
4 5 6 7 4導出の続き：
n + 1 ≤ 2^(h+1)
log₂(n + 1) ≤ h + 1
h ≥ log₂(n + 1) - 1
hは少なくともlog₂(n)でなければならないので、h = O(log n)ステップ3：実数での具体例
7ノードの木（完全バランス）：
1 高さ = 2
/ \ 各レベルのノード：
2 3 レベル0：1ノード
/| |\ レベル1：2ノード
4 5 6 7 レベル2：4ノード
合計：7ノード = 2^3 - 1
高さ：2 = floor(log₂(7)) ✓
1,000,000ノードの木：
log₂(1,000,000) ≈ 19.93
高さ ≈ 20レベル
1,000,000,000ノードの木（10億）：
log₂(1,000,000,000) ≈ 29.9
高さ ≈ 30レベルステップ4：DFS空間計算量への影響
DFSはルートから現在のノードまでの現在のパスのみをコールスタックに格納します：
DFS走査中のコールスタック：
[root] → 1フレーム（ルートで）
[root, left] → 2フレーム（左の子で）
[root, left, left.left] → 3フレーム（left.leftの子で）
...
[root, ..., leaf] → h+1フレーム（最も深い葉で）
最大スタックフレーム = 高さ + 1 = バランス木の場合O(log n)ノード数対高さの視覚的比較：
ノード数 (n) | 高さ (h) | 必要なスタックフレーム
------------- | -------- | -------------------
7 | 2 | 3
15 | 3 | 4
31 | 4 | 5
1,023 | 9 | 10
1,048,575 | 19 | 20
1,073,741,823 | 29 | 3010億を超えるノードでも、30個のスタックフレームしか必要ありません！これが対数成長の力です - 高さはノード数よりもはるかにゆっくり成長します。
なぜコールスタックが私たちの味方なのか
DFSの素晴らしさは、コールスタックが自動的に以下を提供することです：
- 戻る場所の記憶 - ブランチの探索を終えたとき、スタックは正確にどこを中断したかを知っている
- 暗黙のバックトラッキング - 「どこに戻るか」を手動で追跡する必要がない
- 自然な深さ制限 - スタックオーバーフローは実際には無限再帰を防ぐ機能
各再帰呼び出しはスタックに1つのフレームを追加するだけです：
explore(root) // スタック：[root]
explore(left) // スタック：[root, left]
explore(left.left) // スタック：[root, left, left.left]
return // スタック：[root, left] - 自動バックトラック！
explore(left.right) // スタック：[root, left, left.right]
return // スタック：[root, left]
return // スタック：[root]
explore(right) // スタック：[root, right]保証：すべてのノードは正確に1回訪問され、使用される最大メモリは木の総サイズではなく、高さに比例します。グラフの場合、訪問済みセットにより、ノードを2回処理することがなくなり、無限ループが完全に排除されます。