JavaScriptのグラフ（Graph）データ構造入門：基本概念から実装まで徹底解説

グラフ（Graph）とは、複数のオブジェクトの集合を図式化したもので、一部のオブジェクト同士がリンク（線）によって接続されたデータ構造です。相互に接続されたオブジェクトは頂点と呼ばれる点で表現され、頂点同士をつなぐリンクは辺と呼ばれます。

形式的に定義すると、グラフは2つの集合のペア (V, E) として表されます。ここで V は頂点の集合、E は頂点同士を接続する辺の集合です。次のグラフを見てみましょう。

上記のグラフでは、以下のように表されます。

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

グラフの重要な用語

数学的なグラフは、データ構造としてプログラム上で表現できます。具体的には、頂点を格納する配列と、辺を表す二次元配列を組み合わせて実装するのが一般的です。解説を進める前に、まず押さえておきたい重要な用語を確認しましょう。

• 頂点 − グラフを構成する各ノードを指します。下図の例では、ラベル付きの円がそれぞれ頂点を表しており、AからGまですべて頂点です。これらは配列として管理でき、たとえばAはインデックス0、Bはインデックス1というように識別できます。

• 辺 − 2つの頂点をつなぐ線、すなわち2つの頂点間の経路を表します。下図の例では、AからB、BからCへ伸びる線などがすべて辺に該当します。二次元配列で表現する場合、ABは「行0・列1」に1を設定し、BCは「行1・列2」に1を設定するように記録し、それ以外の組み合わせは0とします。

• 隣接 − 2つのノード（頂点）が1本の辺で直接つながっている状態を指します。下図の例では、BはAに隣接し、CはBに隣接していることになります。

• パス（経路） − 2つの頂点をつなぐ一連の辺の並びを表します。下図の例では、ABCDが「AからDへのパス」に相当します。

JavaScriptによるGraphクラスの実装例

以下は、JavaScriptでGraphクラスを完全に実装したサンプルコードです。基本的なノード・辺の追加に加え、幅優先探索（BFS）、深さ優先探索（DFS）、トポロジカルソート、最短経路探索、さらにプリム法やクラスカル法による最小全域木（MST）、ダイクストラ法、ワーシャル・フロイド法まで、代表的なグラフアルゴリズムを網羅しています。

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: weight });
        this.edges[node2].push({ node: node1, weight: weight });
    }

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

    display() {
        let graph = "";
        this.nodes.forEach(node => {
            graph += node + "->" + this.edges[node].map(n => n.node).join(", ") + "\n";
        });
        console.log(graph);
    }

    BFS(node) {
        let q = new Queue(this.nodes.length);
        let explored = new Set();
        q.enqueue(node);
        explored.add(node);
        while (!q.isEmpty()) {
            let t = q.dequeue();
            console.log(t);
            this.edges[t].filter(n => !explored.has(n)).forEach(n => {
                explored.add(n);
                q.enqueue(n);
            });
        }
    }

    DFS(node) {
        // スタックを作成し、初期ノードを追加
        let s = new Stack(this.nodes.length);
        let explored = new Set();
        s.push(node);

        // 最初のノードを探索済みとしてマーク
        explored.add(node);

        // スタックが空になるまで処理を続ける
        while (!s.isEmpty()) {
            let t = s.pop();

            // スタックから取り出した要素を出力
            console.log(t);

            // 1. 隣接するノードを取得
            // 2. 探索済みのノードを除外
            // 3. 未探索ノードをマークしてスタックに積む
            this.edges[t].filter(n => !explored.has(n)).forEach(n => {
                explored.add(n);
                s.push(n);
            });
        }
    }

    topologicalSortHelper(node, explored, s) {
        explored.add(node);
        this.edges[node].forEach(n => {
            if (!explored.has(n)) {
                this.topologicalSortHelper(n, explored, s);
            }
        });
        s.push(node);
    }

    topologicalSort() {
        let s = new Stack(this.nodes.length);
        let explored = new Set();
        this.nodes.forEach(node => {
            if (!explored.has(node)) {
                this.topologicalSortHelper(node, explored, s);
            }
        });
        while (!s.isEmpty()) {
            console.log(s.pop());
        }
    }

    BFSShortestPath(n1, n2) {
        let q = new Queue(this.nodes.length);
        let explored = new Set();
        let distances = { n1: 0 };
        q.enqueue(n1);
        explored.add(n1);
        while (!q.isEmpty()) {
            let t = q.dequeue();
            this.edges[t].filter(n => !explored.has(n)).forEach(n => {
                explored.add(n);
                distances[n] = distances[t] == undefined ? 1 : distances[t] + 1;
                q.enqueue(n);
            });
        }
        return distances[n2];
    }

    primsMST() {
        // 最小全域木を格納するグラフを初期化
        const MST = new Graph();
        if (this.nodes.length === 0) {
            return MST;
        }

        // 最初のノードを起点として選択
        let s = this.nodes[0];

        // 優先度付きキューと探索済みセットを作成
        let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
        let explored = new Set();
        explored.add(s);
        MST.addNode(s);

        // 起点ノードからの全エッジを重みを優先度としてキューに追加
        this.edges[s].forEach(edge => {
            edgeQueue.enqueue([s, edge.node], edge.weight);
        });

        // 最小のエッジを取り出して新しいグラフに追加
        let currentMinEdge = edgeQueue.dequeue();
        while (!edgeQueue.isEmpty()) {
            // 未探索ノードにつながるエッジが見つかるまでエッジを除去
            while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
                currentMinEdge = edgeQueue.dequeue();
            }
            let nextNode = currentMinEdge.data[1];
            // キューが空になった場合も考慮して再チェック
            if (!explored.has(nextNode)) {
                MST.addNode(nextNode);
                MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);

                // 再び全エッジを優先度付きキューに追加
                this.edges[nextNode].forEach(edge => {
                    edgeQueue.enqueue([nextNode, edge.node], edge.weight);
                });

                // このノードを探索済みとしてマーク
                explored.add(nextNode);
                s = nextNode;
            }
        }
        return MST;
    }

    kruskalsMST() {
        // 最小全域木を格納するグラフを初期化
        const MST = new Graph();

        this.nodes.forEach(node => MST.addNode(node));
        if (this.nodes.length === 0) {
            return MST;
        }

        // 優先度付きキューを作成
        let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);

        // 全エッジをキューに追加
        for (let node in this.edges) {
            this.edges[node].forEach(edge => {
                edgeQueue.enqueue([node, edge.node], edge.weight);
            });
        }
        let uf = new UnionFind(this.nodes);

        // 全ノードを探索するかキューが空になるまでループ
        while (!edgeQueue.isEmpty()) {
            // 分割代入でエッジ情報を取得
            let nextEdge = edgeQueue.dequeue();
            let nodes = nextEdge.data;
            let weight = nextEdge.priority;

            if (!uf.connected(nodes[0], nodes[1])) {
                MST.addEdge(nodes[0], nodes[1], weight);
                uf.union(nodes[0], nodes[1]);
            }
        }
        return MST;
    }

    djikstraAlgorithm(startNode) {
        let distances = {};

        // 直前のノードへの参照を保存
        let prev = {};
        let pq = new PriorityQueue(this.nodes.length * this.nodes.length);

        // startNode以外の距離を無限大に設定
        distances[startNode] = 0;
        pq.enqueue(startNode, 0);

        this.nodes.forEach(node => {
            if (node !== startNode) distances[node] = Infinity;
            prev[node] = null;
        });

        while (!pq.isEmpty()) {
            let minNode = pq.dequeue();
            let currNode = minNode.data;
            let weight = minNode.priority;

            this.edges[currNode].forEach(neighbor => {
                let alt = distances[currNode] + neighbor.weight;
                if (alt < distances[neighbor.node]) {
                    distances[neighbor.node] = alt;
                    prev[neighbor.node] = currNode;
                    pq.enqueue(neighbor.node, distances[neighbor.node]);
                }
            });
        }
        return distances;
    }

    floydWarshallAlgorithm() {
        let dist = {};
        for (let i = 0; i < this.nodes.length; i++) {
            dist[this.nodes[i]] = {};

            // 既存のエッジにはその重みを設定
            this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));

            this.nodes.forEach(n => {
                // それ以外のノードには無限大を設定
                if (dist[this.nodes[i]][n] == undefined)
                    dist[this.nodes[i]][n] = Infinity;
                // 自己ループの距離は0
                if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
            });
        }

        this.nodes.forEach(i => {
            this.nodes.forEach(j => {
                this.nodes.forEach(k => {
                    // i→k→j の経路が i→j の直行より短ければ更新
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                });
            });
        });
        return dist;
    }
}

class UnionFind {
    constructor(elements) {
        // 分離された成分の数
        this.count = elements.length;

        // 連結成分を追跡
        this.parent = {};
        // 全要素の親を自分自身として初期化
        elements.forEach(e => (this.parent[e] = e));
    }

    union(a, b) {
        let rootA = this.find(a);
        let rootB = this.find(b);

        // ルートが同じなら既に連結済み
        if (rootA === rootB) return;

        // 常に小さい方のルートを親にする
        if (rootA < rootB) {
            if (this.parent[b] != b) this.union(this.parent[b], a);
            this.parent[b] = this.parent[a];
        } else {
            if (this.parent[a] != a) this.union(this.parent[a], b);
            this.parent[a] = this.parent[b];
        }
    }

    // ノードの最終的な親を返す
    find(a) {
        while (this.parent[a] !== a) {
            a = this.parent[a];
        }
        return a;
    }

    // 2ノードの連結性を判定
    connected(a, b) {
        return this.find(a) === this.find(b);
    }
}