ストレージ構造
グラフを保存するには、グラフにノードとエッジの両方があることがわかります。電動グラフの場合、各エッジにも重量値があります。一般的に使用されるグラフストレージ構造には、主に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言語の説明に関するこの記事のすべての内容です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。