重み付きグラフの表現

重み付けされたエッジは隣接リストに保存できます。

重み付きグラフには、頂点重み付けとエッジ重み付けの 2 種類があります。 頂点重み付けグラフでは、各頂点に重みが割り当てられます。 エッジ加重グラフでは、各エッジに重みが割り当てられます。 2 つのタイプのうち、エッジ加重グラフの方がより多くの用途があります。この章では、エッジ加重グラフについて説明します。

重み付きグラフは、エッジの重みを表現する必要がある点を除いて、重み付けされていないグラフと同じ方法で表現できます。重み付けされていないグラフと同様に、重み付けされたグラフの頂点は配列に格納できます。このセクションでは、重み付きグラフのエッジの 3 つの表現を紹介します。

重み付けされたエッジの表現: エッジ配列

重み付けされたエッジは、2 次元配列を使用して表現できます。たとえば、下図 (b) の配列を使用して、下図 (a) のグラフ内のすべてのエッジを格納できます。

重みは、Integer、Double、BigDecimal などの任意のタイプにすることができます。 Object タイプの 2 次元配列を使用して、次のように重み付けされたエッジを表すことができます。

オブジェクト[][] エッジ = {
{新しい Integer(0)、新しい Integer(1)、新しい SomeTypeForWeight(2)}、
{新しい Integer(0)、新しい Integer(3)、新しい SomeTypeForWeight(8)}、
...
};

重み付けされた隣接行列

グラフには n 個の頂点があると仮定します。 2 次元の n * n 行列、たとえば weights を使用して、エッジの重みを表すことができます。 weights[i][j] はエッジの重み (i、j) を表します。頂点 i と j が接続されていない場合、weights[i][j] は null になります。たとえば、上図 (a) のグラフの重みは、隣接行列を使用して次のように表すことができます。

隣接リスト

エッジを表現する別の方法は、エッジをオブジェクトとして定義することです。 AbstractGraph.Edge クラスは、AbstractGraph.java で重み付けされていないエッジを表すために定義されました。重み付けされたエッジの場合、以下のコードに示すように WeightedEdge クラスを定義します。

AbstractGraph.Edge は、AbstractGraph クラスで定義された内部クラスです。頂点 u から v までのエッジを表します。 WeightedEdge は、新しいプロパティ weight を使用して AbstractGraph.Edge を拡張します。

WeightedEdge オブジェクトを作成するには、new WeightedEdge(i, j, w) を使用します。w はエッジの重み (i) 、j)。多くの場合、エッジの重みを比較する必要があります。このため、WeightedEdge クラスは Comparable インターフェイスを実装します。

重み付けされていないグラフの場合、エッジを表すために隣接リストを使用します。重み付きグラフの場合は、引き続き隣接リストを使用します。下の図 a のグラフの頂点の隣接リストは次のように表すことができます。

java.util.List[] list = new java.util.List[5];

list[i] は、頂点 i に隣接するすべてのエッジを保存します。

柔軟性を高めるために、次のように list を表すために固定サイズの配列ではなく配列リストを使用します。

リスト<リスト<加重エッジ>> list = 新しい java.util.ArrayList<>();

以上が重み付きグラフの表現の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。