## Javaにおける重み付きグラフの構築 ### Javaにおける重み付きグラフの表現 Javaでは、隣接行列または隣接リストを使って重み付きグラフを表現できます。これら2つの表現の選択は、グラフのサイズ、辺の更新頻度、および実行する操作の種類など、アプリケーションの特定の要件に依存します。 #### 隣接行列表現隣接行列は2次元配列で、各要素が2つのノード間の辺の重みを表します。2つのノード間に辺がない場合、行列内の対応する要素は通常0または大きな値（例：`Integer.MAX_VALUE`）に設定されて接続のないことを示します。以下は、Javaで隣接行列を使って重み付きグラフを表現する方法の例です： ```java int[][] adjacencyMatrix = { {0, 5, 3, 0}, {5, 0, 2, 1}, {3, 2, 0, 4}, {0, 1, 4, 0} }; ``` #### 隣接リスト表現隣接リストは、リンクリストまたは配列のコレクションで、各リンクリストまたは配列がノードの隣接ノードと対応する辺の重みを表します。以下は、Javaで隣接リストを使って重み付きグラフを表現する方法の例です： ```java Map> adjacencyList = new HashMap<>(); adjacencyList.put(0, new ArrayList<>(Arrays.asList( new WeightedEdge(1, 5), new WeightedEdge(2, 3) ))); adjacencyList.put(1, new ArrayList<>(Arrays.asList( new WeightedEdge(0, 5), new WeightedEdge(2, 2), new WeightedEdge(3, 1) ))); adjacencyList.put(2, new ArrayList<>(Arrays.asList( new WeightedEdge(0, 3), new WeightedEdge(1, 2), new WeightedEdge(3, 4) ))); adjacencyList.put(3, new ArrayList<>(Arrays.asList( new WeightedEdge(1, 1), new WeightedEdge(2, 4) ))); ``` この例では、`WeightedEdge`クラスは、ソースノード、宛先ノード、および重みを持つ辺を表すカスタムクラスです。 ### Javaにおける重み付きグラフの構築 Javaで重み付きグラフを構築するには、要件に応じて隣接行列または隣接リスト表現を使えます。以下は、隣接リスト表現を使って重み付きグラフを作成する方法の例です： ```java public class WeightedGraph { private Map>> adjacencyList; public WeightedGraph() { adjacencyList = new HashMap<>(); } public void addVertex(T vertex) { adjacencyList.putIfAbsent(vertex, new ArrayList<>()); } public void addEdge(T source, T destination, double weight) { if (!adjacencyList.containsKey(source)) { addVertex(source); } if (!adjacencyList.containsKey(destination)) { addVertex(destination); } adjacencyList.get(source).add(new WeightedEdge<>(destination, weight)); } // 他のメソッド、例えばgetNeighbors、getWeightなど } ``` この例では、`WeightedGraph`クラスは重み付きグラフの隣接リスト表現を格納するために`Map`を使っています。`addVertex`メソッドはグラフに新しいノードを追加し、`addEdge`メソッドは2つのノード間に新しい重み付き辺を追加します。