グラフアルゴリズムシリーズ: 無向グラフのデータ構造

[[393944]]

この記事はWeChatの公開アカウント「Beta Learns JAVA」から転載したもので、著者はSilently9527です。この記事を転載する場合は、Beta Learning JAVA パブリックアカウントにお問い合わせください。

序文

この記事から、グラフ関連のアルゴリズムを一緒に学習します。グラフコンピューティングには、ガベージコレクターのマークアンドスイープアルゴリズム、マップ上のパスの最短距離、トポロジカルソートなど、非常に実用的なアルゴリズムが多数あります。これらのアルゴリズムを学習する前に、まずグラフの基本的な定義と、グラフを表すために使用されるデータ構造を理解する必要があります。この記事では、無向グラフから始めます。

グラフの定義

グラフ: 頂点の集合と、2 つの順序を接続できる順序の集合で構成されます。 2 つの頂点を結ぶ辺には方向がなく、このようなグラフは無向グラフと呼ばれます。

グラフ用語

同じ辺で接続された 2 つの頂点は隣接していると呼ばれます。

頂点の次数とは、この頂点を結ぶ辺の総数です。上図に示すように、頂点1の次数は3です。

頂点をそれ自身に接続する辺は自己ループと呼ばれます。

同じ頂点のペアを結ぶ辺は平行辺と呼ばれる。

他にもたくさんの用語があります。今のところ、この記事で使用する必要のある用語のみをリストします。他の用語については後で説明します。用語が多すぎると覚えるのは簡単ではありません。

グラフの表現方法

グラフを表現するために使用されるデータ構造は、主に次の 2 つの要件を指します。

グラフ関連のアルゴリズムを開発する場合、グラフ表現のデータ構造が基礎となるため、このデータ構造が効率的です。
実際のプロセスでは、グラフのサイズは不確実であり、非常に大きくなる可能性があるため、十分なスペースを確保する必要があります。

これら 2 つの要件を考慮した後、専門家は次の 3 つの選択方法を提案しました。

隣接行列は、v 個の頂点を持つグラフに入力されます。v に v を掛けた行列を使用して表すことができます。頂点 v が w に接続されている場合は、v 行と w 列を true に設定します。これにより、2 つの頂点が接続されていることが示されます。ただし、この方法には問題があります。グラフが非常に大きい場合、スペースが無駄になります。 2番目のポイントは満たされていません。第二に、この方法では平行なエッジを表現することができない。
エッジの配列は、頂点を表す 2 つの int 属性を含むエッジオブジェクトを定義できます。ただし、頂点の接続された頂点を見つける必要がある場合は、すべてのエッジをトラバースする必要があります。このデータ構造は効率が悪い
隣接リスト配列は、頂点の数と同じサイズの配列を定義します。データの添え字は頂点を表します。配列内の各要素はリンクリストオブジェクト (LinkedListQueue) であり、リンクリストに格納されている値は、頂点に接続されている頂点です。 (LinkedListQueueは以前の記事で実装されています。記事「https://juejin.cn/post/6926685994347397127」を参照してください)

無向グラフのAPI定義

パブリッククラスGraph {
 public Graph( int V); // v 個の頂点と辺のないグラフを作成する
     
公共  int V(); //頂点の数を返す
     
公共  int E(); //グラフ内のエッジの総数を返す
     
 public void addEdge( int v, int w); //グラフにエッジvWを追加する
         
 public Iterable< Integer > adj( int v); // v に隣接するすべての頂点を返す
     
 public String toString(); //文字列を使用してグラフの関係を出力します
}

無向グラフAPIの実装

上記で定義した API を実装するには、3 つのメンバー変数が必要です。v はグラフ内の頂点の数を表し、e はグラフの合計エッジデータを表し、LinkedListQueue 配列は頂点 v の隣接ノードを格納するために使用されます。

コンストラクタは空の隣接リスト配列を初期化する

これは無向グラフなので、addEdge メソッドはグラフに v->w エッジと w->v エッジの両方を追加する必要があります。

パブリッククラスGraph {
    プライベート最終int v;
    プライベートint e;
    プライベート LinkedListQueue< Integer >[] adj; 
 
パブリックグラフ( int v) {
        this.v = v;
        this.adj = (LinkedListQueue< Integer >[]) 新しいLinkedListQueue[v];
 ( int i = 0; i < v; i++)の場合{
            this.adj[i] = 新しいLinkedListQueue<>();
        }
    } 
 
公共 整数V(){
 vを返します。
    } 
 
公共 整数E() {
 eを返します。
    } 
 
パブリックvoid addEdge( int v, int w) {
        this.adj[v].enqueue(w);
        this.adj[w].enqueue(v);
        this.e++;
    } 
 
パブリックイテラブル<整数> adj( int v) {
 this.adj[v]を返します。
    } 
 
    @オーバーライド
パブリック文字列toString() {
        StringBuilder sb = 新しい StringBuilder();
        sb.append(v).append( " 頂点、 " ).append(e).append( " 辺\n" );
 ( int i = 0; i < v; i++)の場合{
            sb.append(i).append( ": " );
 ( int j : this.adj[i])の場合{
                sb.append(j).append( " " );
            }
            sb.append( "\n" );
        }
 sb.toString()を返します。
    }
 }

グラフの一般的なツールと方法

グラフデータ構造の実装に基づいて、いくつかのツールと方法を提供することができます。

頂点 v の次数を計算します。頂点の次数は、その頂点に接続されている頂点の数に等しくなります。

公共 静的  int degree(グラフグラフ、 int v) {
度数= 0;
 ( int w : graph.adj(v))の場合{
        学位++;
    }
戻り度合い;
 }

すべての頂点の最大次数を計算する

公共 静的  int maxDegree(グラフグラフ) {
最大度数= 0;
 ( int v = 0; v < graph.V(); v++)の場合{
 int度 = 度(グラフ、v);
        （最大度数<度数）の場合{
            最大度数 = 度数;
        }
    }
 maxDegreeを返します。
 }

すべての頂点の平均次数を計算します。各辺には 2 つの頂点があるため、グラフ内のすべての頂点の合計次数は辺の 2 倍になります。

公共 静的  double avgDegree(グラフグラフ) {
 2.0 * graph.E() / graph.V()を返します。
 }

グラフ内の自己ループの数を計算します。頂点 v について、v が v の隣接リストにも表示される場合、v には自己ループがあります。無向グラフであるため、各エッジは 2 回記録されます (理解しにくい場合は、グラフの toString を出力して理解することができます)

公共 静的  int numberOfSelfLoops(グラフグラフ) {
整数 カウント= 0;
 ( int v = 0; v < graph.V(); v++)の場合{
 ( int w : graph.adj(v))の場合{
            (v == w) の場合 {
カウント++;
            }
        }
    }
戻る カウント/ 2;
 }