ストレージ構造
グラフを保存するには、グラフにノードとエッジの両方があることがわかります。電動グラフの場合、各エッジにも重量値があります。一般的に使用されるグラフストレージ構造には、主に2つのタイプがあります。
隣接するマトリックス隣接テーブル
隣接するマトリックス
ノードを表すために、1次元配列でそれらを表すことができることを知っています。ただし、ノード間の関係については、1次元配列でそれらを単純に表すことはできません。それらを2次元配列、つまりマトリックス形成表現法で表すことができます。
Aはこの2次元配列であり、Aの要素AIJがノードVIとノードVJの関係を反映するだけでなく、AIJの値も重量のサイズを表すことができると仮定します。
これは、無向グラフの隣接マトリックス表現の例です。
上記の図から、無向グラフの隣接マトリックスは対称行列であり、対称行列でなければならないことがわかります。左上隅から右下隅までの対角線の値はゼロです（対角線は同じノードを示します）
指示されたグラフの隣接マトリックスは何ですか？
加重グラフの場合、AIJの値を使用して、重量のサイズを表すことができます。上記の2つのグラフは、重みのないグラフであるため、値は両方とも1です。
隣接するテーブル
グラフの隣接マトリックスストレージメソッドがn*nマトリックスを使用することを知っています。このマトリックスが密なマトリックスである場合（たとえば、グラフが完全なグラフである場合）、もちろん、隣接マトリックスストレージ方法が選択されます。
しかし、このマトリックスがスパースマトリックスである場合、隣接するテーブルストレージ構造は、よりスペースを節約するストレージ構造です。
上記の無向グラフの場合、隣接テーブルを使用して次のように表現できます。
各ノードに接続されたノードは、隣接するノードです。
隣接マトリックスと隣接テーブルの比較
グラフ内のノードの数が小さく、多くの側面がある場合、隣接マトリックスを使用する効率が高くなります。
ノードの数が非常に大きく、エッジの数が同じノードの完全なグラフのエッジ数よりもはるかに少ない場合、隣接するテーブルストレージ構造を採用する方が効率的です。
隣接マトリックスのJava実装
隣接するマトリックスモデルクラス
隣接マトリックスモデルクラスのクラス名はamwgraph.javaです。このクラスを介して隣接マトリックスで表されるグラフを作成し、挿入ノードを提供し、エッジを挿入し、最初の隣接ノードと特定のノードの次の隣接ノードを取得できます。
Java.util.arraylist; Import Java.util.linkedList;/** * @description隣接マトリックスモデルクラス * @author beanlam * @time 20155.4.17 */public class amwgraph {private arraylist vertexlist;パブリックamwgraph（int n）{//マトリックス、1次元配列、およびエッジの数を初期化しますエッジ= new int [n] [n]; vertexlist = new ArrayList（n）; numofedges = 0; } //ノードの数を取得しますpublic int getNumofvertex（）{return vertexlist.size（）; } // edgesの数を取得しますpublic int getnumofedges（）{return numofedges; } //ノードのデータを返しますi public object getValueByIndex（int i）{return vertexlist.get（i）; } // V1、V2 public int getWeight（int v1、int v2）{return edges [v1] [v2]; } //ノードパブリックvoid insertervertex（object Vertex）{vertexlist.add（vertexlist.size（）、vertex）; } // insert node public void insertedge（int v1、int v2、int weight）{edges [v1] [v2] = weight; numofedges ++; } //削除ノードpublic void deleteedge（int v1、int v2）{edges [v1] [v2] = 0; numofedges--; } //最初の隣接ノードパブリックint getFirstneighbor（int index）{for（int j = 0; j <vertexlist.size（）; j ++）{if（edges [index] [j]> 0）{return j; }} return -1; } //以前の隣接ノードパブリックint getnextneighbor（int v1、int v2）{for（int j = v2+1; j <vertexlist.size（）; j ++）{for（edges [v1] [j]> 0）{return j; }} return -1; }}隣接マトリックスモデルクラスのテスト
次に、次の指示グラフに基づいてテストモデルクラスを設定します
testamwgraph.javaテストプログラムは次のとおりです。
/** * @description amwgraph class * @author beanlam * @time 20155.4.17 */public class testamwgraph {public static void main（string args []）{int n = 4、e = 4; //それぞれノードの数とそれぞれエッジの数を表します。ラベル[] = {"v1"、 "v1"、 "v3"、 "v4"}; //ノード識別amwgraphグラフ= new amwgraph（n）; for（string label：labels）{graph.insertvertex（label）; // insert node} // 4つのエッジgraph.insertedge（0、1、2）; graph.insertedge（0、2、5）; graph.insertedge（2、3、8）; graph.insertedge（3、0、7）; System.out.println（ "ノードの数は次のとおりです。 System.out.println（ "エッジの数は次のとおりです。 graph.deleteedge（0、1）; // delete <v1、v2> edge system.out.println（ "削除後<v1、v2> edge ..."）; System.out.println（ "ノードの数は次のとおりです。 System.out.println（ "エッジの数は次のとおりです。 }}コンソールの出力結果を以下の図に示します。
要約します
上記は、ストレージ構造と隣接マトリックスコードの例のJava言語の説明に関するこの記事のすべての内容です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。