データ構造とアルゴリズム: グラフ構造

写真

グラフ構造は、ツリー構造よりも複雑な非線形構造です。ツリー構造では、ノード間に分岐階層関係があります。各層のノードは、前の層のノードのうち最大 1 つにのみ関連付けることができますが、次の層のノードは複数に関連付けることができます。グラフ構造では、任意の 2 つのノードが関連付けられる可能性があり、つまり、ノード間の隣接関係は任意になります。

したがって、グラフ構造はさまざまな複雑なデータオブジェクトを記述するために使用され、自然科学、社会科学、人文科学などの多くの分野で非常に幅広く応用されています。グラフ構造は、コンピュータサイエンス、人工知能、電子回路解析、最短経路探索、エンジニアリング計画、化合物分析、統計力学、遺伝学、サイバネティクス、言語学、社会科学など、さまざまな分野で使用されています。グラフ構造は、あらゆるデータ構造の中で最も広く使用されていると言えます。地下鉄駅の路線図など：

グラフの定義

グラフは、ノードが 0 個以上の隣接要素を持つことができるデータ構造です。2 つのノード間の接続はエッジと呼ばれます。グラフ構造内のノードは頂点とも呼ばれ、1 つの頂点から別の頂点までの線はパスと呼ばれます。

グラフ構造には、無向グラフ、有向グラフ、重み付きグラフの 3 種類があります。
無向グラフ: 頂点 A と頂点 B の間の辺は無向であり、A から B へ、または B から A へ向かうことができます。
有向グラフ: 頂点 A と頂点 B の間の辺は有向であり、A から B へは行けるが、B から A へは行けない。
重み付きグラフ: 頂点 A と頂点 B 間のエッジには、A から B までの距離などの属性があります。

グラフの表現方法

グラフを表現する方法は2つあります。隣接行列（2次元配列を使用）と隣接リスト（配列+リンクリストを使用）です。

隣接行列

隣接行列はグラフ内の頂点間の関係を表します。行列の行と列は頂点に対応し、座標位置の値はそれらの間の関係に対応し、接続の場合は 1、接続なしの場合は 0 になります。プログラムでは2次元配列を使用して実装されます。

隣接リスト

隣接リストは存在するエッジのみを対象とし、存在しないエッジにスペースを割り当てる必要はありません。したがって、隣接行列と比較して、不必要なスペースの浪費を回避できます。プログラムでは、配列 + リンクリストの形式で実装されています。配列には対応する頂点が格納され、リンクリストには頂点に接続されたすべての頂点が格納されます。

グラフ検索アルゴリズム

グラフィックス構造の基本的なプロパティとメソッド

以下のコードデモンストレーションはすべて隣接行列式の形式で実装されています。

 //グラフ構造（隣接行列）
クラスグラフ{
     //グラフ内のすべての頂点を保存する
    プライベートList<String>頂点;
    //グラフ構造の隣接行列
    プライベートint [][] 行列;
    //各頂点の訪問ステータス。trueは訪問済み、 falseは訪問されていないことを意味します。
    プライベートブール値[] 訪問済み; 
 
    /**
     * 渡された頂点情報に基づいて行列を生成する
     * @param s
     */
パブリックグラフ(文字列s[]) {
        頂点 = 新しいArrayList<>();
 (文字列頂点: s){
            vertexes.add (頂点) ;
        }
        行列 = 新しいint [s.length][s.length];
    } 
 
    /**
     * 2つの頂点を接続してエッジを生成します
     * @param index1 コレクション内の頂点のインデックス
     * @param インデックス2
     */
パブリックvoid connect ( intインデックス1、 intインデックス2) {
        if (index1 < 0 || index1 > 行列の長さ || index2 < 0 || index2 > 行列の長さ){
            新しい RuntimeException( "頂点が存在しません" ) をスローします。
        }
        //新しい隣接性を隣接行列に追加する
        行列[インデックス1][インデックス2] = 1;
        行列[インデックス2][インデックス1] = 1;
    } 
 
    /**
     * 隣接行列を表示する
     */
パブリックvoid showGraphMatrix(){
 ( int arr[] : 行列) {
            System.out.println (Arrays.toString(arr)) ;
        }
    } 
     
    /**
     * 隣接行列の対応する行の最初の隣接頂点の添え字を取得します。
     * @param 行
     * @return隣接する頂点がある場合はその頂点のインデックスを返し、そうでない場合は -1 を返します。
     */
公共  int getFirstNeighbor( int row){
 ( int i =0; i<matrix.length; i++) {
            （行列[行][i] != 0）の場合{
 iを返します。
            }
        }
 -1 を返します。
    } 
 
    /**
     * 隣接行列の列colの行の頂点の次の隣接頂点を取得します。
     * @param 行
     * @param 列
     * @return隣接する頂点がある場合はその頂点のインデックスを返し、そうでない場合は -1 を返します。
     */
公共  int getNeighbor( int行, int列){
 ( int i=col+1; i<matrix.length; i++) {
            （行列[行][i] != 0）の場合{
 iを返します。
            }
        }
 -1 を返します。
    }
 }

深さ優先探索

深さ優先探索はグラフアルゴリズムの一種で、DFS (Depth First Search) と略されます。簡単に言うと、このプロセスは、それ以上深く探索できなくなるまですべての可能な分岐パスを探索し、各ノードには 1 回しかアクセスできないというものです。このようなアクセス戦略では、頂点のすべての隣接頂点への水平アクセスではなく、垂直掘削が優先されます。簡単に言えば、最後まで道を進み、うまくいかなかったら引き返すことを意味します。

アイデア: 現在の頂点に接続されているがまだ訪問されていない頂点を選択し、現在のノードを隣接する頂点に移動します。訪問されていない隣接する頂点がない場合は、前の頂点の位置に戻ってこの手順を続行します。すべての頂点が訪問されるまで。

隣接しているがまだ訪問していない頂点に移動する

未訪問の隣接頂点は存在しないため、未訪問の隣接頂点に遭遇するまで戻ります。

すべての頂点を訪問したら、アルゴリズムを終了します。

以下は深さ優先探索プロセスのアニメーションです。

コードデモンストレーション

パブリックvoid dsf(){
    訪問 = 新しいブール値[ vertexes.size ()];
    // セット内のインデックス 0 の頂点を使用して深さ検索を実行します
    dsf(訪問数, 0);
 } 
 
 /**
 * 深さ優先探索
 * @param 訪問済み
 * @param 行
 */
パブリックvoid dsf(boolean[] 訪問済み、 int行){
    // 現在の頂点を出力する
    システム.out.print (vertexes.get(row) + " -> " );
    //現在の頂点を訪問済みに設定する
    訪問[行] = true ;
    //現在の頂点の隣接頂点の添え字を取得します
整数 インデックス= getFirstNeighbor(行);
    //現在の頂点に隣接する頂点がある場合は、深度検索を実行します
    while (インデックス!= -1){
        //隣接する頂点が訪問されていない場合は、再帰的に走査します
        if (visited[インデックス] != true ){
            dsf(訪問、インデックス);
        }
        //隣接する頂点が訪問されたら、別の隣接する頂点を見つける
インデックス= getNeighbor(行、インデックス);
    }
 }

幅優先探索

幅優先探索アルゴリズム (幅優先探索とも呼ばれる) は、最も単純なグラフ検索アルゴリズムの 1 つであり、多くの重要なグラフアルゴリズムのプロトタイプでもあります。ダイクストラの単一ソース最短経路アルゴリズムとプリムの最小全域木アルゴリズムはどちらも幅優先探索に似た考え方を採用しています。別名は BFS とも呼ばれ、グラフ内のすべてのノードを体系的に拡張してチェックし、結果を見つけることを目的としたブラインド検索方法です。つまり、結果の可能性のある場所を考慮せず、結果が見つかるまでグラフ全体を徹底的に検索します。

幅優先探索アルゴリズムは、階層的探索プロセスに似ています。幅優先探索アルゴリズムでは、訪問した頂点の順序を維持するためのキューが必要であり、これにより、これらの頂点の隣接頂点をこの順序で訪問できるようになります。

アイデア: 現在の頂点の隣接頂点を順番に訪問し、訪問順にこれらの隣接頂点をキューに格納します。現在の頂点のすべての隣接頂点を訪問したら、キューから頂点をポップし、すべての頂点を訪問するまで、その頂点を現在の頂点としてこの手順を続けます。

現在の頂点の隣接する頂点を順に訪問し、訪問順にこれらの隣接する頂点をキューに格納します。

現在の頂点には、未訪問の隣接頂点がありません。キューから頂点をポップし、ポップした頂点を使用して、未訪問の隣接頂点の訪問を続行します。

グラフ内のすべての頂点が訪問済みであっても、アルゴリズムはキュー内のすべての頂点がポップアウトされて訪問されるまで待機してから終了する必要があることに注意してください。

以下は幅優先探索プロセスのアニメーションです。

コードデモンストレーション

パブリックボイドbfs(){
    訪問 = 新しいブール値[ vertexes.size ()];
    ////セット内のインデックス0の頂点に対して幅優先探索を実行します
    bfs(訪問数, 0);
 } 
 
 /**
 * 幅優先探索
 * @param 訪問済み
 * @param 行
 */
パブリックvoid bfs(boolean[] 訪問済み、 int行){
    //隣接する頂点を走査する順序を格納するキューを作成する
    LinkedList キュー = new LinkedList();
    // 現在の頂点を出力する
    システム.out.print (vertexes.get(row) + " -> " );
    //現在の頂点を訪問済みに設定する
    訪問[行] = true ;
    //現在の頂点をキューに追加します
    キューに行を追加します。
    //キューが空でない場合、つまり未検索の隣接頂点がある場合、検索
    while (!queue.isEmpty()){
        // キューから隣接する頂点インデックスを順番にポップアップします
整数 最後= (整数)queue.removeFirst();
        //ポップアップ頂点の隣接頂点の添え字を取得します
整数 インデックス= getFirstNeighbor(最後);
        //ポップアップ頂点に隣接する頂点がある場合は、幅検索を実行します
        while(インデックス!=-1){
            //隣接する頂点が訪問されていない場合
            if(visited[インデックス]!= true ){
                // 隣接する頂点を出力する
                システム.out.print (vertexes.get( index )+ "->" );
                //隣接する頂点を訪問済みに設定する
                訪問[インデックス] = true ;
                //隣接する頂点をキューに追加します
                キューに最後にインデックスを追加します。
            }
            //ポップアップ頂点の別の隣接頂点を探し続けます
インデックス= getNeighbor(最後、インデックス);
        }
    }
 }

完全なデモコード

パブリッククラスGraphDemo {
公共 静的void main(String[] args) {
        文字列[] s = { "A" 、 "B" 、 "C" 、 "D" 、 "E" 、 "F" 、 "G" };
        グラフ graph = 新しいグラフ;
        //AB AC AG AF FD FE DE EG
        グラフに接続します(0, 1);
        グラフに接続します(0, 2);
        グラフに接続します(0, 6);
        グラフに接続します(0, 5);
        グラフに接続します(5, 3);
        グラフに接続します(5, 4);
        グラフに接続します(3, 4);
        グラフ.connect (4, 6);
        グラフマトリックスを表示します。 
 
        graph.dsf(); //A -> B -> C -> F -> D -> E -> G ->
        System.out.println( ) ;
        graph.bfs(); //A -> B -> C -> F -> G -> D -> E ->
    }
 } 
 
 //グラフィック構造
クラスグラフ{
    //グラフ内のすべての頂点を保存する
    プライベートList<String>頂点;
    //グラフ構造の隣接行列
    プライベートint [][] 行列;
    //各頂点の訪問ステータス。trueは訪問済み、 falseは訪問されていないことを意味します。
    プライベートブール値[] 訪問済み; 
 
    /**
     * 渡された頂点情報に基づいて行列を生成する
     * @param s
     */
パブリックグラフ(文字列s[]) {
        頂点 = 新しいArrayList<>();
 (文字列頂点: s){
            vertexes.add (頂点) ;
        }
        行列 = 新しいint [s.length][s.length];
    } 
 
    /**
     * 2つの頂点を接続してエッジを生成します
     * @param index1 コレクション内の頂点のインデックス
     * @param インデックス2
     */
パブリックvoid connect ( intインデックス1、 intインデックス2) {
        if (index1 < 0 || index1 > 行列の長さ || index2 < 0 || index2 > 行列の長さ){
            新しい RuntimeException( "頂点が存在しません" ) をスローします。
        }
        //新しい隣接性を隣接行列に追加する
        行列[インデックス1][インデックス2] = 1;
        行列[インデックス2][インデックス1] = 1;
    } 
 
    /**
     * 隣接行列を表示する
     */
パブリックvoid showGraphMatrix(){
 ( int arr[] : 行列) {
            System.out.println (Arrays.toString(arr)) ;
        }
    } 
 
パブリックvoid dsf(){
        訪問 = 新しいブール値[ vertexes.size ()];
        // セット内のインデックス 0 の頂点に対して深さ優先探索を実行します
        dsf(訪問数, 0);
    } 
 
    /**
     * 深さ優先探索
     * @param 訪問済み
     * @param 行
     */
パブリックvoid dsf(boolean[] 訪問済み、 int行){
        // 現在の頂点を出力する
        システム.out.print (vertexes.get(row) + " -> " );
        //現在の頂点を訪問済みに設定する
        訪問[行] = true ;
        //現在の頂点の隣接頂点の添え字を取得します
整数 インデックス= getFirstNeighbor(行);
        //現在の頂点に隣接する頂点がある場合は、深度検索を実行します
        while (インデックス!= -1){
            //隣接する頂点が訪問されていない場合は、再帰的に走査します
            if (visited[インデックス] != true ){
                dsf(訪問、インデックス);
            }
            //隣接する頂点が訪問されたら、別の隣接する頂点を見つける
インデックス= getNeighbor(行、インデックス);
        }
    } 
 
パブリックボイドbfs(){
        訪問 = 新しいブール値[ vertexes.size ()];
        ////セット内のインデックス0の頂点に対して幅優先探索を実行します
        bfs(訪問数, 0);
    } 
 
    /**
     * 幅優先探索
     * @param 訪問済み
     * @param 行
     */
パブリックvoid bfs(boolean[] 訪問済み、 int行){
        //隣接する頂点を走査する順序を格納するキューを作成する
        キュー queue = new ArrayDeque();
        // 現在の頂点を出力する
        システム.out.print (vertexes.get(row) + " -> " );
        //現在の頂点を訪問済みに設定する
        訪問[行] = true ;
        //現在の頂点をキューに追加します
        キューに行を追加します。
        //キューが空でない場合、つまり未検索の隣接頂点がある場合、検索
        while (!queue.isEmpty()){
            // キューから隣接する頂点インデックスを順番にポップアップします
整数  last = (整数)queue.poll();
            //ポップアップ頂点の隣接頂点の添え字を取得します
整数 インデックス= getFirstNeighbor(最後);
            //ポップアップ頂点に隣接する頂点がある場合は、幅検索を実行します
            while(インデックス!=-1){
                //隣接する頂点が訪問されていない場合
                if(visited[インデックス]!= true ){
                    // 隣接する頂点を出力する
                    システム.out.print (vertexes.get( index )+ "->" );
                    //隣接する頂点を訪問済みに設定する
                    訪問[インデックス] = true ;
                    //隣接する頂点をキューに追加します
                    キューに追加(インデックス)
                }
                //ポップアップ頂点の別の隣接頂点を探し続けます
インデックス= getNeighbor(最後、インデックス);
            }
        }
    } 
 
    /**
     * 隣接行列の対応する行の最初の隣接頂点の添え字を取得します。
     * @param 行
     * @return隣接する頂点がある場合はその頂点のインデックスを返し、そうでない場合は -1 を返します。
     */
公共  int getFirstNeighbor( int row){
 ( int i =0; i<matrix.length; i++) {
            （行列[行][i] != 0）の場合{
 iを返します。
            }
        }
 -1 を返します。
    } 
 
    /**
     * 隣接行列の列colの行の頂点の次の隣接頂点を取得します。
     * @param 行
     * @param 列
     * @return隣接する頂点がある場合はその頂点のインデックスを返し、そうでない場合は -1 を返します。
     */
公共  int getNeighbor( int行, int列){
 ( int i=col+1; i<matrix.length; i++) {
            （行列[行][i] != 0）の場合{
 iを返します。
            }
        }
 -1 を返します。
    }
 }