データ構造とアルゴリズム: 最小全域木、数秒で理解できます!

[[426679]]

序文

データ構造とアルゴリズムのグラフ理論において、最小全域木アルゴリズムは、比較的実生活に近い一般的なアルゴリズムです。しかし、多くの人はこの概念をあまり明確に理解していないかもしれません。最小全域木とは何でしょうか?

n 個のノードを持つ接続グラフの全域木は、元のグラフの n 個のノードすべてを含み、グラフの接続を維持するために必要な最小数のエッジを持つ、元のグラフの最小の接続サブグラフです。最小全域木は、クラスカルアルゴリズムまたはプリムアルゴリズムを使用して見つけることができます。

簡単に言えば、最小全域木には元のグラフのすべてのノードが含まれますが、最小のエッジと最小の重み距離のみが使用されます。 n 個のノードを接続するには少なくとも n-1 個のエッジが必要であり、距離に応じて適切なエッジを選択するための特定の戦略が必要になるためです。

最小全域木の実装アルゴリズムを学習する前に、まず最小全域木の構造と重要性を理解する必要があります。より理解を深めるために、まずは写真をいくつか見てみましょう。

物語

都市道路計画は非常に科学的な研究テーマです（真剣に取り組む必要はないと想定してください）。高速道路時代において、都市の接続性における主な矛盾は時間の遅さであり、輸送時間と比較するとコストは二次的な矛盾です。そのため、高速道路の時代には、都市を直接接続し、都市間の時間を短縮し、道路建設のコストのみを考慮するように努めています。科学技術の発展に伴い、鉄道は先進的になり、情報伝達は道路輸送よりもはるかに高速になったため、イベントの主な矛盾は輸送時間から建設コストに移行しました。そのため、すべてのポイントを結ぶ距離（最短）に注目することもあり、これには最小全域木アルゴリズムが使用されます。

都市の道路舗装は、以下の段階を経ることがあります。

当初、都市には高速道路（鉄道）はありませんでした。
政府は各都市に道路（鉄道）を建設する計画を立てています。どの都市も交通の要衝となり、他の都市に早く到達したいと考えていますが、どの都市もこの考えを持っており、実現すればコストが高すぎます。そしてそれは莫大な無駄を生み出します。
最終的に、国は接続のためにいくつかの主要都市を選択し、いくつかの個々の都市はわずかな迂回でしか接続できませんでした。人口の流れが大きく、迂回が遠すぎる国では、効率を適切に改善するために新しい道路（鉄道）が検討されます。

しかし、人口が膨大であるため、上記の鉄道計画では「鉄道」の需要に応えられない可能性があります。人々は速度、距離、直通などの条件を追求してきましたが...

しかし、次のようなシナリオを想像してみてください。偽造には非常に費用がかかるものの、使用すると非常に効率的であるものがあります。ここでは、それらが金やダイヤモンドで覆われたケーブルであると想定しています。そのため、各都市は遅れを取らずに通過することだけを求めます（誰も飛び降りる勇気はありません）。

巡回グラフからコストが最も低いルートを選択するには、一方ではコストが最も低く（総距離が最も短く、ゴールドが最も節約される）、他方ではすべての都市が接続される必要があります。

ただし、上の図によれば、次の最小全域木が得られますが、この最小全域木を生成する方法については、以下で説明します。

同様の高コストな方法としては、一部の地域で島々を結ぶ橋を建設したり、海底通路を建設したりすることがあり、多かれ少なかれ利用されることになるだろう。

クラスカルアルゴリズム

上記では、最小全域木とは何かを紹介しました。次に、最小全域木がどのように形成されるかを習得し、理解する必要があります。グラフが与えられたら、ルールを使用して最小全域木を生成します。最小全域木の実装に関しては、プリムアルゴリズムとクラスカルアルゴリズムがあります。これら 2 つのアルゴリズムの戦略は異なりますが、時間の計算量は同じです。

クラスカルアルゴリズムは、上記の結合検索アルゴリズムと密接に関連しています。その主な考え方は次のとおりです。

まず、n 個の頂点と空のエッジセットのみを持つサブグラフを構築します。サブグラフ内の各頂点を各ツリーのルートノードとして扱います。次に、ネットワークのエッジセット E から最小の重みを持つエッジを選択します。このエッジの 2 つの頂点が異なるツリーに属している場合は、サブグラフに追加します。つまり、2 つのツリーを 1 つのツリーにマージします。逆に、このエッジの 2 つの頂点がすでに同じツリーに属している場合は、お勧めできません。最小の重みを持つ次のエッジを選択して再試行する必要があります。これを繰り返して、フォレスト内のツリーが 1 本だけになり、サブグラフに n-1 個のエッジが含まれるようになります。

つまり、クラスカルアルゴリズムのスケジューリングの単位はエッジです。すべてのエッジは可能な限り小さくできると想定されています。アルゴリズムの実装では、union-find を使用して、2 つのポイントが同じセット内にあるかどうかを判断します。

アルゴリズムの具体的な手順は次のとおりです。

グラフ内のすべてのエッジオブジェクト（エッジの長さ、2つの端点）をセット（優先キュー）q1に順番に追加します。最初はすべてのポイントは互いに独立しています。
集合（優先キュー）の最小のエッジq1を取り出し、エッジの2点が接続されているかどうかを判定します。
接続されている場合は、2 つのポイントを接続する他のエッジがあることを意味するため、それをスキップします。接続されていない場合は、union (union-find union) を使用して 2 つの頂点を結合し、このエッジを使用します (値を保存または計算するため)。
セット（優先キュー）q1が空になるまで、操作2と3を繰り返します。このとき選択されたエッジは最小全域木を形成します。

クラスカルアルゴリズムに加えて、プリムアルゴリズムもよく使用される最小全域木アルゴリズムです。効率は同様ですが。しかし、貪欲なアプローチはクラスカルのアプローチとはまったく異なります。

プリムのアルゴリズムの核となる考え方は、既知の拡散から最小値を見つけることです。その実装は Dijkstra アルゴリズムに似ていますが、少し異なります。Dijkstra は単一のソースからの最短経路を見つけ、ポイントが計算されるたびにポイントの距離を再度更新する必要がありますが、prim では距離を更新する必要はありません。既知の点の最小の隣接エッジを見つけて追加するだけです。プリムアルゴリズムとクラスカルアルゴリズムはどちらもエッジから始まります。

特定のアルゴリズムの具体的な手順は、おおよそ次のようになります。

グラフ内の任意の点を見つけて、それを開始点として、そのすべてのエッジ V をセット (優先キュー) q1 に追加し、ブール配列 bool[] を設定して位置をマークします (エッジには 2 つの点があり、そのたびにその点でマークされていないすべてのエッジが追加されます)。
集合 q1 から最短距離のエッジ v1 を探し、そのエッジ上にマークされていない点 `p` があるかどうかを判定します。p が存在しない場合は、決定済みであることを意味するため、現在のエッジ処理をスキップします。マークされていない (訪問されていない) 場合は、点 p をマークし、p に接続された未知の点 (マークされていない) によって形成されるエッジを集合 q1 に追加します。エッジ v1 (距離の計算などが可能で、このエッジは最小全域木を形成します)。
q1 が空になるまで 1 と 2 を繰り返し、最小全域木を形成します。

一般的な手順は次のようになります。

プリムは最初から最後まで全体として広がっているので、2 つのツリーのマージを考慮する必要がなく、実装が少し簡単になります。

もちろん、最小全域木は一意ではなく、同じアルゴリズムで生成された最小全域木であっても異なる場合があることに注意する必要がありますが、どのような最小全域木が生成されても、次のことは同じです。

すべてのノードが接続されていることを確認する機能（要件と条件を満たすことができる）
すべてのパスの合計が最小になるようにする機能（同じ結果と目的）
最小全域木は一意ではなく、多様である可能性がある

コードの実装

論理的な実装は上記で分析されています。以下では、コードを使用して上記のアルゴリズムを簡単に実装します。

プリム

パッケージ グラフ理論; 
 
 java.util.ArrayList をインポートします。
 java.util.Arrays をインポートします。
 java.util.Comparator をインポートします。
 java.util.List をインポートします。
 java.util.PriorityQueue をインポートします。
 java.util.Queue をインポートします。 
 
パブリッククラス prim { 
 
公共 静的void main(String[] args) {
 int minlength=0; //最小全域木の最短経路長
整数 最大値=66666;
        文字列 cityname[] = { "北京" 、 "武漢" 、 "南京" 、 "上海" 、 "杭州" 、 "広州" 、 "深セン" };
 int都市[][]= {
                { max , 8, 7, max , max , max , max }, //北京と武漢の南京聯通
                { 8,最大、6,最大、9, 8,最大}, //武漢 - 北京、南京、杭州、広州
                { 7, 6, max , 3,4, max , max }, // 南京 - 北京、武漢、上海、杭州
                { max , max ,3, max ,2, max , max }, //上海——南京、杭州
                { max , 9,4, 2, max , max ,10 }, //杭州 - 武漢、南京、上海、深セン
                { max , 8, max , max , max , max ,2 }, //広州 - 武漢、深セン
                { max , max , max , max ,10,2, max }//深セン——杭州、広州
        }; // マップ
 
        ブール値istrue[]=新しいブール値[7];
        //南京
        Queue<side>q1=新しいPriorityQueue<side>(新しいComparator<side>() {
公共  int compare(サイドo1、サイドo2) {
                // TODO 自動生成されたメソッドスタブ
o1.lenth-o2.lenthを返します。
            }
        });
 ( int i=0;i<7;i++ )の場合
        {
            都市[2][i]!=最大)
            {
                istrue[2] =真;
                q1. (新しいサイド(city[2][i], 2, i))を追加します。
            }
        }
        while(!q1.isEmpty())
        {
            サイドnewside=q1.poll();//throw
            if(istrue[newside.point1]&&istrue[newside.point2])
            {
続く;
            }
それ以外{
                if(!istrue[newside.point1])
                {
                    istrue[newside.point1] = true ;
                    最小長さ+=city[newside.point1][newside.point2];
                    システム.out.println (cityname[newside.point1]+ " " +cityname[newside.point2]+ " China Unicom" );
 ( int i=0;i<7;i++ )の場合
                    {
                        if(!istrue[i])
                        {
                            q1. (new side(city[newside.point1][i],newside.point1,i))を追加します。
                        }
                    }
                }
それ以外{
                    istrue[newside.point2] = true ;
                    最小長さ+=city[newside.point1][newside.point2];
                    システム.out.println (cityname[newside.point2]+ " " +cityname[newside.point1]+ " China Unicom" );
 ( int i=0;i<7;i++ )の場合
                    {
                        if(!istrue[i])
                        {
                            q1. (new side(city[newside.point2][i],newside.point2,i))を追加します。
                        }
                    }
                }
            } 
 
        }
        System.out.println (最小長さ) ;
    } 
 
静的クラス side//side
    {
 int長さ;
ポイント1;
ポイント2;
パブリックサイド( int長さ, int p1, int p2) {
            this.lenth=長さ;
            ポイント1 = p1;
            ポイント2 = p2;
        }
    } 
 
 }

出力：

上海南京聯通
杭州上海聯通
武漢南京聯通
北京南京聯通
広州武漢聯通
深セン広州聯通
28

クラスカル：

パッケージ グラフ理論; 
 
 java.util.Comparator をインポートします。
 java.util.PriorityQueue をインポートします。
 java.util.Queue をインポートします。 
 
 graphtheory.prim.side をインポートします。
 /*
 * 作者: bigsai (公開アカウント)
 */
パブリッククラスkruskal { 
 
静的  int tree[]=new int [10]; //bing検索
公共 静的void init() {
 for ( int i=0;i<10;i++)//初期値
        {
            木[i]=-1;
        }
    }
公共 静的  int search( int a) //ヘッドノードの値を返す
    {
        if(tree[a]>0) // 子ノードであることを示します
        {
 return tree[a]=search(tree[a]);//パス圧縮
        }
それ以外 
を返します。
    }
公共  static void union ( int a, int b) // a と b が配置されているツリーが、小さなツリーと大きなツリーにマージされることを意味します (重要ではありません)
    {
 int a1=search(a); //ルート
int b1=search(b); //b ルート
        if(a1==b1){// System.out.println (a+ "と" +b+ "はすでに同じツリー内にあります" );
        }
それ以外{
        if(tree[a1]<tree[b1]) //これは負の数です。計算を減らすために、値関数は呼び出されません。
        {
            tree[a1]+=tree[b1]; // 数字を足します。負の数であることに注意してください。
            tree[b1]=a1; //ツリーbはaのサブツリーになり、aを直接指します。
        }
それ以外 
        {
            tree[b1]+=tree[a1]; //数字を足します。負の数であることに注意してください。
            tree[a1]=b1; //ツリーbはaのサブツリーになり、aを直接指します。
        }
        }
    }
公共 静的void main(String[] args) {
        // TODO 自動生成されたメソッドスタブ
        初期化();
 int minlength=0; //最小全域木の最短経路長
整数 最大値=66666;
        文字列 cityname[] = { "北京" 、 "武漢" 、 "南京" 、 "上海" 、 "杭州" 、 "広州" 、 "深セン" };
        boolean jud[][]=new boolean[7][7]; // エッジを追加する場合は重複を防ぐ必要があります。たとえば、baとabは同等です。
 int都市[][]= {
                {最大、8、7、最大、最大、最大、最大},
                { 8,最大、6,最大、9, 8,最大},
                { 7, 6,最大, 3,4,最大,最大},
                {最大、最大、3、最大、2、最大、最大},
                {最大、9,4、2、最大、最大、10 },
                {最大、8、最大、最大、最大、最大、2 },
                {最大、最大、最大、最大、10、2、最大}
        }; // マップ
        ブール値istrue[]=新しいブール値[7];
        //南京
        Queue<side>q1=new PriorityQueue<side>(new Comparator<side>(){//優先キューはside + を保存します。
公共  int compare(サイドo1、サイドo2) {
                // TODO 自動生成されたメソッドスタブ
o1.lenth-o2.lenthを返します。
            }
        });
 ( int i=0;i<7;i++ )の場合
        {
 ( int j=0;j<7;j++)の場合
            {
                if(!jud[i][j]&&city[i][j]!= max )//キューに参加するかどうか
                {
                    jud[i][j] =真;jud[j][i] =真;
                    q1. (新しいサイド(city[i][j], i, j))を追加します。
                }
            }
        }
        while(!q1.isEmpty())//アルゴリズムを実行
        {
            サイドnewside=q1.poll();
 p1 = newside.point1;
 p2 = newside.point2;
            if(検索(p1)!=検索(p2))
            {
結合（p1、p2）;
                システム.out.println (cityname[p1]+ " " +cityname[p2]+ " China Unicom" );
                最小長さ+=新しいサイドの長さ;
            }
        }
        System.out.println (最小長さ) ; 
 
 
    }
静的クラス side//side
    {
 int長さ;
ポイント1;
ポイント2;
パブリックサイド( int長さ, int p1, int p2) {
            this.lenth=長さ;
            ポイント1 = p1;
            ポイント2 = p2;
        }
    }
 }

出力

上海杭州聯通
広州深セン聯通
南京上海聯通
武漢南京聯通
北京南京聯通
武漢広州聯通
28

要約する

最小全域木アルゴリズムは理解するのが比較的簡単で、実装するのも難しくありません。 Kruskal と Prim は、貪欲アルゴリズムを主に 2 つの観点から検討します。 1 つは全体から始めて最小のエッジを見つけ、関連付けに遭遇したときにそれをマージします。もう 1 つはローカルから始めて拡散し、その周囲の最小値を見つけ、最小全域木が生成されるまで拡散を続けます。実装をより速く、より明確にするために、最小全域木を学習する前に、ダイクストラのアルゴリズムと和集合探索を学習するのが最善です。

LK1584 は最小全域木に関する入門問題ですが、すべての点が接続されていると仮定しているため、刈り込み最適化を実行する必要があるという点が異なります。ここではお見せしません。ご質問があれば、下記からご連絡いただくこともできます！

最後に、もしあなたがいつか本当にそのような高価なゴールデンルートを建設するための大金を手に入れたら、この方法を適切に採用することができます。残りのお金については、あなたがお金持ちになったら忘れないでください。

<<: 将来のAIの世界における興味深い仕事

>>: 2021年9月のドローン業界の最新動向を3分で振り返る