アルゴリズム実装・最適化・実践応用の完全ガイド
トポロジカルソートは、DAGの頂点を線形順序に並べるアルゴリズムです。依存関係を満たす実行順序を決定する際の基礎となります。
class DAG { constructor() { this.adjList = new Map(); this.inDegree = new Map(); } addVertex(vertex) { if (!this.adjList.has(vertex)) { this.adjList.set(vertex, []); this.inDegree.set(vertex, 0); } } addEdge(from, to) { this.addVertex(from); this.addVertex(to); this.adjList.get(from).push(to); this.inDegree.set(to, this.inDegree.get(to) + 1); } topologicalSort() { const result = []; const queue = []; const inDegreeCopy = new Map(this.inDegree); // 入次数0の頂点をキューに追加 for (let [vertex, degree] of inDegreeCopy) { if (degree === 0) { queue.push(vertex); } } while (queue.length > 0) { const current = queue.shift(); result.push(current); // 隣接頂点の入次数を減らす for (let neighbor of this.adjList.get(current)) { inDegreeCopy.set(neighbor, inDegreeCopy.get(neighbor) - 1); if (inDegreeCopy.get(neighbor) === 0) { queue.push(neighbor); } } } return result.length === this.adjList.size ? result : null; } }
DAGでは最長パス問題を多項式時間で解くことができます（一般グラフではNP困難）。
class LongestPath { constructor(dag) { this.dag = dag; this.memo = new Map(); } findLongestPath(start, end) { const topoOrder = this.dag.topologicalSort(); const dist = new Map(); const parent = new Map(); // 初期化 for (let vertex of topoOrder) { dist.set(vertex, vertex === start ? 0 : -Infinity); parent.set(vertex, null); } // トポロジカル順序で処理 for (let u of topoOrder) { if (dist.get(u) !== -Infinity) { for (let v of this.dag.adjList.get(u)) { if (dist.get(u) + 1 > dist.get(v)) { dist.set(v, dist.get(u) + 1); parent.set(v, u); } } } } return this.reconstructPath(start, end, parent, dist); } reconstructPath(start, end, parent, dist) { if (dist.get(end) === -Infinity) return null; const path = []; let current = end; while (current !== null) { path.unshift(current); current = parent.get(current); } return { path: path, length: dist.get(end), distance: dist.get(end) }; } }
データ処理パイプラインにおけるDAGの活用例：依存関係管理、並列実行計画、障害復旧戦略
class DataPipeline { constructor() { this.tasks = new Map(); this.dependencies = new Map(); this.executionPlan = null; } addTask(taskId, processor, resources = {}) { this.tasks.set(taskId, { id: taskId, processor: processor, resources: resources, status: 'pending', startTime: null, endTime: null, error: null }); this.dependencies.set(taskId, []); } addDependency(taskId, dependsOn) { if (!this.dependencies.has(taskId)) { this.dependencies.set(taskId, []); } this.dependencies.get(taskId).push(dependsOn); } generateExecutionPlan() { // トポロジカルソートベースの実行計画 const dag = new DAG(); for (let taskId of this.tasks.keys()) { dag.addVertex(taskId); } for (let [taskId, deps] of this.dependencies) { for (let dep of deps) { dag.addEdge(dep, taskId); } } this.executionPlan = dag.topologicalSort(); return this.executionPlan; } async executeParallel() { const plan = this.generateExecutionPlan(); const executing = new Set(); const completed = new Set(); const canExecute = (taskId) => { return this.dependencies.get(taskId).every(dep => completed.has(dep)); }; while (completed.size < plan.length) { // 実行可能なタスクを特定 const ready = plan.filter(taskId => !executing.has(taskId) && !completed.has(taskId) && canExecute(taskId) ); // 並列実行 const promises = ready.map(async taskId => { executing.add(taskId); try { await this.executeTask(taskId); completed.add(taskId); } catch (error) { this.tasks.get(taskId).error = error; throw error; } finally { executing.delete(taskId); } }); await Promise.all(promises); } } async executeTask(taskId) { const task = this.tasks.get(taskId); task.status = 'running'; task.startTime = Date.now(); try { await task.processor(); task.status = 'completed'; } catch (error) { task.status = 'failed'; task.error = error; throw error; } finally { task.endTime = Date.now(); } } }
| アルゴリズム | 時間計算量 | 空間計算量 | 特徴 | 適用場面 |
|---|---|---|---|---|
| Kahn's Algorithm | O(V + E) | O(V) | キュー使用、安定 | 一般的なトポソート |
| DFS-based TopSort | O(V + E) | O(V) | 再帰、逆順出力 | メモリ効率重視 |
| Longest Path | O(V + E) | O(V) | DP使用 | スケジューリング |
| Critical Path | O(V + E) | O(V) | 最早/最遅時刻計算 | プロジェクト管理 |
n個のタスクがあり、各タスクには実行時間t[i]が設定されています。DAGで表現された依存関係の下で、全タスクの完了時間を最小化する並列実行スケジュールを求めてください。
DAGにおいて、任意の2つの頂点間の到達可能性を前処理O(V²)で計算し、クエリをO(1)で答えるデータ構造を設計してください。