グラフの表現

グラフを表現するとは、その頂点と辺をプログラムに保存することです。グラフを格納するデータ構造は配列またはリストです。グラフを処理および操作するプログラムを作成するには、グラフのデータをコンピュータに保存または表現する必要があります。

頂点の表現

頂点は配列またはリストに保存できます。たとえば、次の配列を使用して、下図のグラフ内のすべての都市名を保存できます:

String[] 頂点 = {"シアトル"、"サンフランシスコ"、"ロサンゼルス"、"デンバー"、"カンザスシティ"、"シカゴ"、"ボストン"、"ニューヨーク"、"アトランタ"、"マイアミ」、「ダラス」、「ヒューストン」};

頂点は、任意のタイプのオブジェクトにすることができます。たとえば、都市をその名前、人口、市長などの情報を含むオブジェクトとして考えることができます。したがって、次のように頂点を定義できます:

都市 city0 = new City("シアトル", 608660, "マイク・マッギン");
...
都市 city11 = new City("ヒューストン", 2099451, "アニス パーカー");
City[] 頂点 = {city0, city1, ... , city11};

パブリッククラス City {
プライベート文字列都市名;
プライベート int 人口;
プライベート文字列市長;

public City(String cityName, int population, String mayor) {
this.cityName = cityName;
this.population = population;
this.mayor = mayor;
 }

public String getCityName() {
return cityName;
 }

public int getPopulation() {
return population;
 }

public String getMayor() {
return mayor;
 }

public void setMayor(String mayor) {
this.mayor = mayor;
 }

public void setPopulation(int population) {
this.population = population;
 }
}

n 個の頂点のグラフでは、自然数 0、1、2、...、n - 1 を使用して頂点にラベルを付けることができます。したがって、vertices[0] は " Seattle" を表し、vertices[1] は "San Francisco" を表し、以下同様になります。以下の図に示されています。

頂点は、名前またはインデックスのどちらか便利な方で参照できます。明らかに、プログラム内のインデックスを介して頂点にアクセスするのは簡単です。

エッジの表現: エッジ配列

エッジは 2 次元配列を使用して表現できます。たとえば、次の配列を使用して、図 28.1 のグラフ内のすべてのエッジを保存できます:

int[][] エッジ = {
{0, 1}、{0, 3}、{0, 5}、
{1, 0}、{1, 2}、{1, 3}、
{2, 1}、{2, 3}、{2, 4}、{2, 10}、
{3, 0}、{3, 1}、{3, 2}、{3, 4}、{3, 5}、
{4, 2}、{4, 3}、{4, 5}、{4, 7}、{4, 8}、{4, 10}、
{5, 0}、{5, 3}、{5, 4}、{5, 6}、{5, 7}、
{6, 5}、{6, 7}、
{7, 4}、{7, 5}、{7, 6}、{7, 8}、
{8, 4}、{8, 7}、{8, 9}、{8, 10}、{8, 11}、
{9, 8}、{9, 11}、
{10, 2}、{10, 4}、{10, 8}、{10, 11}、
{11, 8}、{11, 9}、{11, 10}
};

この表現は、エッジ配列として知られています。下図 (a) の頂点と辺は次のように表すことができます。

String[] names = {"ピーター"、"ジェーン"、"マーク"、"シンディ"、"ウェンディ"};
int[][] エッジ = {{0, 2}, {1, 2}, {2, 4}, {3, 4}};

エッジの表現: エッジ オブジェクト

エッジを表現する別の方法は、エッジをオブジェクトとして定義し、エッジを java.util.ArrayList に保存することです。 Edge クラスは次のように定義できます:

パブリック クラス Edge {
int u;
int v;
public Edge(int u, int v) {
this.u = u;
this.v = v;
}
public booleanquals(Object o) {
return u == ((エッジ)o).u && v == ((エッジ)o).v;
}
}

たとえば、次のリストを使用して、下図のグラフ内のすべてのエッジを保存できます。

java.util.ArrayList list = 新しい java.util.ArrayList<>();
list.add(new Edge(0, 1));
list.add(new Edge(0, 3));
list.add(new Edge(0, 5));
...

Edge オブジェクトを ArrayList に保存すると、エッジが事前にわからない場合に便利です。

前のセクション (エッジの表現: エッジ配列) およびこのセクションの前半でエッジ配列または エッジ オブジェクトを使用してエッジを表現することは、入力にとっては直感的かもしれませんが、入力には効率的ではありません。内部処理。次の 2 つのセクションでは、隣接行列 と 隣接リスト を使用したグラフの表現を紹介します。これら 2 つのデータ構造は、グラフの処理に効率的です。

エッジの表現: 隣接行列

グラフには n 個の頂点があると仮定します。 2 次元の n * n 行列、たとえば adjacencyMatrix を使用してエッジを表すことができます。配列内の各要素は 0 または 1 です。 adjacencyMatrix[i][j] は、頂点 i から頂点 j までのエッジがある場合、1 です。それ以外の場合、adjacencyMatrix[i][j] は 0 です。グラフが無向の場合、adjacencyMatrix[i][j] は adjacencyMatrix[j][i] と同じであるため、行列は対称になります。たとえば、次の図のグラフのエッジは、隣接行列を使用して次のように表すことができます。

int[][] adjacencyMatrix = {
{0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // シアトル
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // サンフランシスコ
{0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // ロサンゼルス
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // デンバー
{0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // カンザスシティ
{1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // シカゴ
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // ボストン
{0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // ニューヨーク
{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // アトランタ
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // マイアミ
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // ダラス
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // ヒューストン
};

無向グラフでは行列が対称であるため、ストレージを節約するために不規則な配列を使用できます。

下図 (a) の有向グラフの隣接行列は次のように表すことができます。

int[][] a = {{0, 0, 1, 0, 0}, // ピーター
{0, 0, 1, 0, 0}, // ジェーン
{0, 0, 0, 0, 1}, // マーク
{0, 0, 0, 0, 1}, // シンディ
{0, 0, 0, 0, 0} // ウェンディ
};

エッジの表現: 隣接リスト

隣接頂点 リストまたは 隣接エッジ リスト を使用してエッジを表すことができます。頂点 i の隣接頂点リストには i に隣接する頂点が含まれ、頂点 i の隣接エッジ リストには i に隣接するエッジが含まれます。リストの配列を定義できます。
配列には n 個のエントリがあり、各エントリはリストです。頂点 i の隣接頂点リストには、頂点 i から頂点 j までのエッジが存在するすべての頂点 j が含まれます。たとえば、以下の図のグラフのエッジを表すには、次のようにリストの配列を作成できます。

java.util.List[] 近隣 = new java.util.List[12];

neighbors[0] には頂点 0 (つまりシアトル) に隣接するすべての頂点が含まれ、neighbors[1] には頂点 1 (つまり、サンフランシスコ) など、以下の図に示すように。