JavaScriptでグラフを作成する方法｜隣接リストによる有向・無向グラフの実装

本記事では、重み（ウェイト）や有向・無向の両方のグラフに対応できるGraphクラスをJavaScriptで作成します。実装には「隣接リスト」というデータ構造を採用しています。重みや有向性をサポートしておくことで、最短経路探索（ダイクストラ法）など、より高度なアルゴリズムへ発展させる際にもそのまま活用できます。

隣接リストとは

隣接リストとは、個別のリストからなる配列でグラフを表現する方法です。配列の各要素 Ai はリストになっており、頂点 i に隣接しているすべての頂点を格納しています。これにより、ノード同士の接続関係を効率よく管理することができます。

今回は、nodes（ノードの一覧）と edges（各ノードの接続情報）という2つのメンバーを持つオブジェクトとして、隣接リストを定義します。

Graphクラスの実装

それでは、クラス本体と、グラフにノードやエッジ（辺）を追加するためのメソッドを定義しながら、Graphクラスを構築していきましょう。最初に用意するのは以下の3つのメソッドです。

• addNode：グラフに新しいノードを追加する
• addEdge：無向エッジ（双方向の辺）を追加する
• addDirectedEdge：有向エッジ（一方向の辺）を追加する

コード例

class Graph {
   constructor() {
      this.edges = {};
      this.nodes = [];
   }
   addNode(node) {
      this.nodes.push(node);
      this.edges[node] = [];
   }
   addEdge(node1, node2) {
      this.edges[node1].push(node2);
      this.edges[node2].push(node1);
   }
   addDirectedEdge(node1, node2) {
      this.edges[node1].push(node2);
   }
   display() {
      let graph = ""; this.nodes.forEach(node => {
         graph += node + "->" + this.edges[node].join(", ") + "\n";
      });
      console.log(graph);
   }
}

各メソッドの役割は次のとおりです。addNode はノードを配列に登録すると同時に、空の接続リストを初期化します。addEdge は双方のノードにお互いを登録するため無向の辺となり、addDirectedEdge は片方向のみ登録するため有向の辺になります。また、display メソッドを使えば、現在のグラフの状態をコンソールで確認できます。

動作確認

作成したクラスと各メソッドは、以下のコードでテストできます。

コード例

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
 
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addDirectedEdge("A", "D");
g.addEdge("D", "E");

g.display();

出力結果

上記のコードを実行すると、コンソールに以下のような隣接リスト形式の出力が表示されます。

A->C, B, D
B->A
C->A
D->E
E->D

この出力から、グラフの構造を読み取ることができます。「A」はC・Bと無向で接続されており、さらに有向エッジによってDへの一方通行の接続も持っています。「D」と「E」はお互いを参照し合っているため、無向の辺で結ばれていることが分かります。