グラフの表現

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

頂点の表現

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

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 (つまり、サンフランシスコ) など、以下の図に示すように。

下図のグラフの隣接エッジ リストを表すには、次のようにリストの配列を作成できます。

java.util.List[] ネイバー = new java.util.List[12];

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

隣接行列または隣接リストを使用してグラフを表すことができます。どちらが良いでしょうか？グラフが密集している (つまり、エッジが多数ある) 場合は、隣接行列を使用することをお勧めします。グラフが非常にまばらである (つまり、エッジが非常に少ない) 場合は、隣接行列を使用すると多くのスペースが無駄になるため、隣接リストを使用する方が良いでしょう。

隣接行列と隣接リストの両方をプログラムで使用して、アルゴリズムをより効率的にすることができます。たとえば、隣接行列を使用して 2 つの頂点が接続されているかどうかを確認するには O(1) の定数時間がかかり、隣接リストを使用してグラフ内のすべてのエッジを出力するには線形時間 O(m) がかかります。ここで、m はエッジの数です。 .

隣接頂点リストは、重み付けされていないグラフを表すためにより簡単です。ただし、隣接エッジ リストは、幅広いグラフ アプリケーションに対してより柔軟です。隣接エッジ リストを使用すると、エッジに追加の制約を簡単に追加できます。このため、本書では隣接エッジ リストを使用してグラフを表現します。

配列、配列リスト、リンク リストを使用して隣接リストを保存できます。リストは簡単に拡張して新しい頂点を追加できるため、配列の代わりにリストを使用します。さらに、アルゴリズムではリスト内の隣接する頂点の検索のみが必要なため、リンク リストの代わりに配列リストを使用します。アルゴリズムでは配列リストを使用する方が効率的です。配列リストを使用すると、下図の隣接エッジ リストを次のように構築できます。

リスト> neighbors = new ArrayList<>();
neighbors.add(new ArrayList());
neighbors.get(0).add(new Edge(0, 1));
neighbors.get(0).add(new Edge(0, 3));
neighbors.get(0).add(new Edge(0, 5));
neighbors.add(new ArrayList());
neighbors.get(1).add(new Edge(1, 0));
neighbors.get(1).add(new Edge(1, 2));
neighbors.get(1).add(new Edge(1, 3));
...
...
neighbors.get(11).add(new Edge(11, 8));
neighbors.get(11).add(new Edge(11, 9));
neighbors.get(11).add(new Edge(11, 10));

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