JavaScript完全グラフクラスの実装

この記事では、JavaScriptで実装された包括的なGraph（グラフ）クラスを紹介します。このクラスは、グラフ理論の主要なアルゴリズムを網羅しており、データ構造の学習や実践的なアプリケーション開発に活用できます。

概要

実装には以下のデータ構造が別モジュールとして分離されており、import文またはrequireで読み込み可能です。

• Queue（キュー） - 幅優先探索用
• Stack（スタック） - 深さ優先探索・トポロジカルソート用
• PriorityQueue（優先度付きキュー） - ダイクストラ法・プリム法・クラスカル法用

Graphクラスの主要メソッド

基本操作

探索アルゴリズム

• BFS(node) - 幅優先探索（キュー使用）
• DFS(node) - 深さ優先探索（スタック使用）
• topologicalSort() - トポロジカルソート（DAG向け）

最短経路アルゴリズム

• BFSShortestPath(n1, n2) - 非重みグラフでの最短経路（BFSベース）
• djikstraAlgorithm(startNode) - ダイクストラ法（重み付きグラフ、非負重み）
• floydWarshallAlgorithm() - フロイド・ウォーシャル法（全点対最短経路）

最小全域木（MST）アルゴリズム

• primsMST() - プリム法（優先度付きキュー使用）
• kruskalsMST() - クラスカル法（Union-Find使用）

UnionFindクラス

クラスカル法で使用されるUnion-Find（離散集合）データ構造も同梱されています。パス圧縮は実装されていませんが、基本的なunion、find、connected操作を提供します。

コード例

const Queue = require("./Queue");
const Stack = require("./Stack");
const PriorityQueue = require("./PriorityQueue");

class Graph {
  constructor() {
    this.edges = {};
    this.nodes = [];
  }

  addNode(node) {
    this.nodes.push(node);
    this.edges[node] = [];
  }

  addEdge(node1, node2, weight = 1) {
    this.edges[node1].push({ node: node2, weight });
    this.edges[node2].push({ node: node1, weight });
  }

  // ... 各アルゴリズムの実装（本文参照）
}

class UnionFind {
  constructor(elements) {
    this.count = elements.length;
    this.parent = {};
    elements.forEach(e => this.parent[e] = e);
  }
  // union, find, connected メソッド
}

使用上の注意

• ノード識別子には文字列や数値など、オブジェクトキーとして有効な値を使用可能
• ダイクストラ法は負の重みを持つ辺には対応していません
• フロイド・ウォーシャル法は計算量がO(V³)のため、大規模グラフには非推奨
• UnionFindのfindメソッドにはパス圧縮が実装されていないため、大規模データでは最適化が必要

拡張のヒント

コメントアウトされている簡易版メソッド（重みなし版）を切り替えることで、用途に応じた軽量実装も可能です。また、TypeScript対応や非同期イテレータ対応、可視化ライブラリとの連携などへの拡張も容易です。