Javaでグラフデータ構造を実装するプログラムの書き方を解説

この記事では、Javaでグラフデータ構造(Graph Data Structure)を実装する方法について詳しく解説します。

グラフとは、頂点(バーテックス/ノード)と、それらを結ぶ辺(エッジ)から構成される非線形データ構造です。隣接リスト形式でグラフを表現する場合、キーと値のペアで要素を管理できるHashMapコレクションを利用する方法があります。本記事ではさらに、各辺の出発点(source)と到達点(destination)を保持するEdgeクラスを定義し、その配列としてグラフ全体を表現するシンプルな実装例を2つのパターンで紹介します。

入力例と出力例

想定する入力:

頂点数: 5
辺数: 8

期待される出力:

グラフのノード間の接続は以下の通りです:
1 - 2
1 - 3
1 - 4
2 - 4
2 - 5
3 - 4
3 - 5
4 - 5

アルゴリズム

1. 処理を開始します。
2. Graphクラスのオブジェクト(graph_object)、Edgeクラス内の整数sourceおよびdestination、main関数内の整数vertices_countおよびedges_countを宣言します。
3. 必要な値を定義します。
4. 頂点数と辺数を初期化します。
5. 定義済みのGraphクラスの新しいインスタンスを生成します。
6. 生成したインスタンスに、各辺の接続情報を設定します。
7. forループでインスタンスを走査し、結果をコンソールに出力します。
8. 結果を表示して処理を終了します。

例1: すべての処理をmain関数にまとめる方法

まず、すべての操作をmain関数の中に直接記述するシンプルな例を示します。

public class Graph {
    class Edge {
        int source, destination;
    }
    int vertices, edges;
    Edge[] edge;
    Graph(int vertices, int edges) {
        this.vertices = vertices;
        this.edges = edges;
        edge = new Edge[edges];
        for(int i = 0; i < edges; i++) {
            edge[i] = new Edge();
        }
    }
    public static void main(String[] args) {
        int vertices_count = 5;
        int edges_count = 8;
        Graph graph_object = new Graph(vertices_count, edges_count);
        System.out.println("A graph object is defined.");
        graph_object.edge[0].source = 1;
        graph_object.edge[0].destination = 2;
        graph_object.edge[1].source = 1;
        graph_object.edge[1].destination = 3;
        graph_object.edge[2].source = 1;
        graph_object.edge[2].destination = 4;
        graph_object.edge[3].source = 2;
        graph_object.edge[3].destination = 4;
        graph_object.edge[4].source = 2;
        graph_object.edge[4].destination = 5;
        graph_object.edge[5].source = 3;
        graph_object.edge[5].destination = 4;
        graph_object.edge[6].source = 3;
        graph_object.edge[6].destination = 5;
        graph_object.edge[7].source = 4;
        graph_object.edge[7].destination = 5;
        System.out.println("The connections between the edges of the Graph are: ");
        for(int i = 0; i < edges_count; i++) {
            System.out.println(graph_object.edge[i].source + " - " + graph_object.edge[i].destination);
        }
    }
}

出力

A graph object is defined.
The connections between the edges of the Graph are:
1 - 2
1 - 3
1 - 4
2 - 4
2 - 5
3 - 4
3 - 5
4 - 5

例2: メソッドにカプセル化する方法(オブジェクト指向)

次に、処理をconnect_edgesメソッドとprintメソッドに分割し、オブジェクト指向プログラミング(OOP)のスタイルで記述した例を示します。この方式では、処理の再利用性とコードの可読性が向上します。

public class Graph {
    class Edge {
        int source, destination;
    }
    int vertices, edges;
    Edge[] edge;
    Graph(int vertices, int edges) {
        this.vertices = vertices;
        this.edges = edges;
        edge = new Edge[edges];
        for(int i = 0; i < edges; i++) {
            edge[i] = new Edge();
        }
    }
    static void print(Graph graph_object,int edges_count){
        System.out.println("The connections between the edges of the Graph are: ");
        for(int i = 0; i < edges_count; i++) {
            System.out.println(graph_object.edge[i].source + " - " + graph_object.edge[i].destination);
        }
    }
    static void connect_edges(Graph graph_object){
        graph_object.edge[0].source = 1;
        graph_object.edge[0].destination = 2;
        graph_object.edge[1].source = 1;
        graph_object.edge[1].destination = 3;
        graph_object.edge[2].source = 1;
        graph_object.edge[2].destination = 4;
        graph_object.edge[3].source = 2;
        graph_object.edge[3].destination = 4;
        graph_object.edge[4].source = 2;
        graph_object.edge[4].destination = 5;
        graph_object.edge[5].source = 3;
        graph_object.edge[5].destination = 4;
        graph_object.edge[6].source = 3;
        graph_object.edge[6].destination = 5;
        graph_object.edge[7].source = 4;
        graph_object.edge[7].destination = 5;
    }
    public static void main(String[] args) {
        int vertices_count = 5;
        int edges_count = 8;
        Graph graph_object = new Graph(vertices_count, edges_count);
        System.out.println("A graph object is defined.");
        connect_edges(graph_object);
        print(graph_object, edges_count);
    }
}

出力

A graph object is defined.
The connections between the edges of the Graph are:
1 - 2
1 - 3
1 - 4
2 - 4
2 - 5
3 - 4
3 - 5
4 - 5

まとめ

このように、Javaでは出発点と到達点を持つEdgeクラスの配列を使うことで、グラフの頂点間の接続関係を簡単に表現できます。基本的な流れは、①Graphクラスのコンストラクタで頂点数と辺数を指定してインスタンスを生成し、②各Edgeに出発点と到達点を設定し、③forループで走査して表示する、という手順です。より実践的な用途では、HashMapやLinkedListを用いた隣接リスト表現を採用すると、動的な頂点・辺の追加や探索処理を効率的に行えます。用途に応じて最適な実装方式を選択してください。