Prim の最小スパニング ツリー (MST) アルゴリズム
Prim のアルゴリズムの概要:
私たちは話し合いました Kruskal の最小スパニング ツリーのアルゴリズム 。 Kruskal のアルゴリズムと同様に、Prim のアルゴリズムも 貪欲なアルゴリズム 。このアルゴリズムは常に 1 つのノードから開始し、途中で接続されているすべてのエッジを探索するために、複数の隣接するノードを通過します。
アルゴリズムは空のスパニング ツリーから始まります。考え方は、2 セットの頂点を維持することです。最初のセットには MST にすでに含まれている頂点が含まれており、もう 1 つのセットにはまだ含まれていない頂点が含まれています。すべてのステップで、2 つのセットを接続するすべてのエッジが考慮され、これらのエッジから最小重みエッジが選択されます。エッジを選択した後、エッジのもう一方の端点を MST を含むセットに移動します。
グラフ内の 2 組の頂点を接続するエッジのグループを といいます。 グラフ理論の切り口 。したがって、Prim のアルゴリズムの各ステップで、カットを見つけ、そのカットから最小ウェイト エッジを選択し、この頂点を MST セット (すでに含まれている頂点を含むセット) に含めます。
Prim のアルゴリズムはどのように機能するのでしょうか?
Prim のアルゴリズムの動作は、次の手順を使用して説明できます。
ステップ1： 任意の頂点を MST の開始頂点として決定します。
ステップ2： MST に含まれていない頂点 (フリンジ頂点と呼ばれる) が存在するまで、手順 3 ～ 5 を実行します。
ステップ 3: 任意のツリー頂点とフリンジ頂点を接続するエッジを見つけます。
ステップ 4: これらのエッジの最小値を見つけます。
ステップ5: 選択したエッジがサイクルを形成しない場合は、MST に追加します。
ステップ6: MST を返して終了します
注記： サイクルを決定するには、頂点を 2 つのセットに分割します (1 つのセットには MST に含まれる頂点が含まれ、もう 1 つはフリンジ頂点が含まれます)。
推奨される実践最小スパニング ツリー 試してみてください。Prim のアルゴリズムの図:
最小スパニング ツリー (MST) を見つける必要がある例として、次のグラフを考えてみましょう。
グラフの例
ステップ1： まず、最小スパニング ツリーの開始頂点として機能する任意の頂点を選択します。ここでは頂点を選択しました 0 開始頂点として。
0 が開始頂点として選択されます
ステップ2： 不完全な MST と他の頂点を接続するすべてのエッジは、エッジ {0, 1} と {0, 7} です。これら 2 つの間で、最小重みを持つエッジは {0, 1} です。したがって、エッジと頂点 1 を MST に含めます。
MSTに1が追加されます
ステップ 3: 不完全な MST を他の頂点に接続するエッジは、{0, 7}、{1, 7}、および {1, 2} です。これらのエッジの中で、最小の重みはエッジ {0, 7} と {1, 2} の 8 です。ここで、エッジ {0, 7} と頂点 7 を MST に含めてみましょう。 [エッジ {1, 2} と頂点 2 を MST に含めることもできました。]
MSTに7が追加されました
ステップ 4: 不完全な MST をフリンジ頂点と接続するエッジは、{1, 2}、{7, 6}、および {7, 8} です。エッジ {7, 6} と頂点 6 を、最小の重み (つまり 1) を持つ MST に追加します。
MSTに6が追加されました
ステップ5: 接続エッジは {7, 8}、{1, 2}、{6, 8}、および {6, 5} になります。エッジ {6, 5} と頂点 5 は、それらの中で最小の重み (つまり 2) を持つため、MST に含めます。
MST に頂点 5 を含める
ステップ6: 現在の接続エッジのうち、エッジ {5, 2} の重みが最小です。したがって、そのエッジと頂点 2 を MST に含めます。
MST に頂点 2 を含める
ステップ 7: 不完全な MST と他のエッジの間の接続エッジは、{2, 8}、{2, 3}、{5, 3}、および {5, 4} です。最小の重みを持つエッジは、重み 2 を持つエッジ {2, 8} です。したがって、このエッジと頂点 8 を MST に含めます。
MST に頂点 8 を追加
ステップ8: ここで、エッジ {7, 8} と {2, 3} は両方とも最小の同じ重みを持っていることがわかります。ただし、7 はすでに MST の一部です。したがって、エッジ {2, 3} を考慮し、そのエッジと頂点 3 を MST に含めます。
MST に頂点 3 を含める
ステップ9: 頂点 4 だけが残ります。不完全な MST から 4 までの最小の重み付きエッジは {3, 4} です。
MST に頂点 4 を含める
MST の最終的な構造は次のとおりで、MST のエッジの重みは (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = となります。 37 。
上記の方法で形成したMSTの構造
注記： 3 番目のステップでエッジ {1, 2} を選択した場合、MST は次のようになります。
MST でエッジ {1, 2} を選択した場合の代替 MST の構造
Prim のアルゴリズムを実装するにはどうすればよいですか?
指定された手順に従って、 プリムのアルゴリズム グラフの MST を見つけるために上で説明したように、
- セットを作成する mstセット MST に既に含まれている頂点を追跡します。
- 入力グラフ内のすべての頂点にキー値を割り当てます。すべてのキー値を INFINITE として初期化します。最初の頂点が最初に選択されるように、キー値を 0 として最初の頂点に割り当てます。
- その間 mstセット すべての頂点が含まれていない
- 頂点を選択してください で それはそこにはありません mstセット 最小キー値を持っています。
- 含む で の中に mstセット 。
- すべての隣接する頂点のキー値を更新します。 で 。キー値を更新するには、隣接するすべての頂点を反復処理します。
- 隣接する頂点ごとに で 、エッジの重さの場合 う～ん 前のキー値より小さいです で 、キーの値を重みとして更新します。 う～ん 。
キー値を使用する考え方は、最小重みエッジを選択することです。 カット 。キー値は、MST にまだ含まれていない頂点に対してのみ使用され、これらの頂点のキー値は、MST に含まれる頂点のセットにそれらを接続する最小重みエッジを示します。
以下はアプローチの実装です。
C++
// A C++ program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> using> namespace> std;> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(> int> key[],> bool> mstSet[])> {> > // Initialize min value> > int> min = INT_MAX, min_index;> > for> (> int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] void printMST(int parent[], int graph[V][V]) { cout < < 'Edge Weight
'; for (int i = 1; i cout < < parent[i] < < ' - ' < < i < < ' ' < < graph[i][parent[i]] < < '
'; } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // Print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; } // This code is contributed by rathbhupendra> |
C
// A C program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> #include> #include> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(> int> key[],> bool> mstSet[])> {> > // Initialize min value> > int> min = INT_MAX, min_index;> > for> (> int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] int printMST(int parent[], int graph[V][V]) { printf('Edge Weight
'); for (int i = 1; i printf('%d - %d %d
', parent[i], i, graph[i][parent[i]]); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; }> |
ジャワ
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency matrix> // representation of the graph> import> java.io.*;> import> java.lang.*;> import> java.util.*;> class> MST {> > // Number of vertices in the graph> > private> static> final> int> V => 5> ;> > // A utility function to find the vertex with minimum> > // key value, from the set of vertices not yet included> > // in MST> > int> minKey(> int> key[], Boolean mstSet[])> > {> > // Initialize min value> > int> min = Integer.MAX_VALUE, min_index = -> 1> ;> > for> (> int> v => 0> ; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST // stored in parent[] void printMST(int parent[], int graph[][]) { System.out.println('Edge Weight'); for (int i = 1; i System.out.println(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]]); } // Function to construct and print MST for a graph // represented using adjacency matrix representation void primMST(int graph[][]) { // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in // cut int key[] = new int[V]; // To represent set of vertices included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = Integer.MAX_VALUE; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count 1; count++) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for // vertices not yet included in MST Update // the key only if graph[u][v] is smaller // than key[v] if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] parent[v] = u; key[v] = graph[u][v]; } } // Print the constructed MST printMST(parent, graph); } public static void main(String[] args) { MST t = new MST(); int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution t.primMST(graph); } } // This code is contributed by Aakash Hasija> |
Python3
# A Python3 program for> # Prim's Minimum Spanning Tree (MST) algorithm.> # The program is for adjacency matrix> # representation of the graph> # Library for INT_MAX> import> sys> class> Graph():> > def> __init__(> self> , vertices):> > self> .V> => vertices> > self> .graph> => [[> 0> for> column> in> range> (vertices)]> > for> row> in> range> (vertices)]> > # A utility function to print> > # the constructed MST stored in parent[]> > def> printMST(> self> , parent):> > print> (> 'Edge Weight'> )> > for> i> in> range> (> 1> ,> self> .V):> > print> (parent[i],> '-'> , i,> ' '> ,> self> .graph[i][parent[i]])> > # A utility function to find the vertex with> > # minimum distance value, from the set of vertices> > # not yet included in shortest path tree> > def> minKey(> self> , key, mstSet):> > # Initialize min value> > min> => sys.maxsize> > for> v> in> range> (> self> .V):> > if> key[v] <> min> and> mstSet[v]> => => False> :> > min> => key[v]> > min_index> => v> > return> min_index> > # Function to construct and print MST for a graph> > # represented using adjacency matrix representation> > def> primMST(> self> ):> > # Key values used to pick minimum weight edge in cut> > key> => [sys.maxsize]> *> self> .V> > parent> => [> None> ]> *> self> .V> # Array to store constructed MST> > # Make key 0 so that this vertex is picked as first vertex> > key[> 0> ]> => 0> > mstSet> => [> False> ]> *> self> .V> > parent[> 0> ]> => -> 1> # First node is always the root of> > for> cout> in> range> (> self> .V):> > # Pick the minimum distance vertex from> > # the set of vertices not yet processed.> > # u is always equal to src in first iteration> > u> => self> .minKey(key, mstSet)> > # Put the minimum distance vertex in> > # the shortest path tree> > mstSet[u]> => True> > # Update dist value of the adjacent vertices> > # of the picked vertex only if the current> > # distance is greater than new distance and> > # the vertex in not in the shortest path tree> > for> v> in> range> (> self> .V):> > # graph[u][v] is non zero only for adjacent vertices of m> > # mstSet[v] is false for vertices not yet included in MST> > # Update the key only if graph[u][v] is smaller than key[v]> > if> self> .graph[u][v]>>> 0> and> mstSet[v]> => => False> > > and> key[v]>>> self> .graph[u][v]:> > key[v]> => self> .graph[u][v]> > parent[v]> => u> > self> .printMST(parent)> # Driver's code> if> __name__> => => '__main__'> :> > g> => Graph(> 5> )> > g.graph> => [[> 0> ,> 2> ,> 0> ,> 6> ,> 0> ],> > [> 2> ,> 0> ,> 3> ,> 8> ,> 5> ],> > [> 0> ,> 3> ,> 0> ,> 0> ,> 7> ],> > [> 6> ,> 8> ,> 0> ,> 0> ,> 9> ],> > [> 0> ,> 5> ,> 7> ,> 9> ,> 0> ]]> > g.primMST()> # Contributed by Divyanshu Mehta> |
C#
// A C# program for Prim's Minimum> // Spanning Tree (MST) algorithm.> // The program is for adjacency> // matrix representation of the graph> using> System;> class> MST {> > // Number of vertices in the graph> > static> int> V = 5;> > // A utility function to find> > // the vertex with minimum key> > // value, from the set of vertices> > // not yet included in MST> > static> int> minKey(> int> [] key,> bool> [] mstSet)> > {> > // Initialize min value> > int> min => int> .MaxValue, min_index = -1;> > for> (> int> v = 0; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print // the constructed MST stored in parent[] static void printMST(int[] parent, int[, ] graph) { Console.WriteLine('Edge Weight'); for (int i = 1; i Console.WriteLine(parent[i] + ' - ' + i + ' ' + graph[i, parent[i]]); } // Function to construct and // print MST for a graph represented // using adjacency matrix representation static void primMST(int[, ] graph) { // Array to store constructed MST int[] parent = new int[V]; // Key values used to pick // minimum weight edge in cut int[] key = new int[V]; // To represent set of vertices // included in MST bool[] mstSet = new bool[V]; // Initialize all keys // as INFINITE for (int i = 0; i key[i] = int.MaxValue; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex // First node is always root of MST key[0] = 0; parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex // from the set of vertices // not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex // to the MST Set mstSet[u] = true; // Update key value and parent // index of the adjacent vertices // of the picked vertex. Consider // only those vertices which are // not yet included in MST for (int v = 0; v // graph[u][v] is non zero only // for adjacent vertices of m // mstSet[v] is false for vertices // not yet included in MST Update // the key only if graph[u][v] is // smaller than key[v] if (graph[u, v] != 0 && mstSet[v] == false && graph[u, v] parent[v] = u; key[v] = graph[u, v]; } } // Print the constructed MST printMST(parent, graph); } // Driver's Code public static void Main() { int[, ] graph = new int[, ] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); } } // This code is contributed by anuj_67.> |
JavaScript
> // Number of vertices in the graph> let V = 5;> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> function> minKey(key, mstSet)> {> > // Initialize min value> > let min = Number.MAX_VALUE, min_index;> > for> (let v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] function printMST(parent, graph) { document.write('Edge Weight' + ' '); for (let i = 1; i document.write(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]] + ' '); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation function primMST(graph) { // Array to store constructed MST let parent = []; // Key values used to pick minimum weight edge in cut let key = []; // To represent set of vertices included in MST let mstSet = []; // Initialize all keys as INFINITE for (let i = 0; i key[i] = Number.MAX_VALUE, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first vertex. key[0] = 0; parent[0] = -1; // First node is always root of MST // The MST will have V vertices for (let count = 0; count { // Pick the minimum key vertex from the // set of vertices not yet included in MST let u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (let v = 0; v // graph[u][v] is non zero only for adjacent vertices of m // mstSet[v] is false for vertices not yet included in MST // Update the key only if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver code let graph = [ [ 0, 2, 0, 6, 0 ], [ 2, 0, 3, 8, 5 ], [ 0, 3, 0, 0, 7 ], [ 6, 8, 0, 0, 9 ], [ 0, 5, 7, 9, 0 ] ]; // Print the solution primMST(graph); // This code is contributed by Dharanendra L V.> |
出力
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5
Prim のアルゴリズムの複雑さの分析:
時間計算量: O(V 2 )、入力の場合 グラフは隣接リストを使用して表現されます の場合、バイナリ ヒープの助けを借りて、Prim のアルゴリズムの時間計算量は O(E * logV) に削減できます。この実装では、スパニング ツリーがグラフのルートから開始されることを常に考慮しています。
補助スペース: O(V)
Prim のアルゴリズムのその他の実装:
以下に、Prim のアルゴリズムの他の実装をいくつか示します。
- 隣接行列表現のための Prim のアルゴリズム – この記事では、グラフが隣接行列で表されている場合にプリムのアルゴリズムを実装する方法について説明しました。
- 隣接リスト表現のための Prim のアルゴリズム – この記事では、隣接リストで表されるグラフに対する Prim のアルゴリズムの実装について説明します。
- Priority Queueを使用したPrimのアルゴリズム: この記事では、Prim のアルゴリズムを実装するための時間効率の高いアプローチについて説明しました。
PRIM のアルゴリズムの最適化されたアプローチ:
直感
- 次を使用して隣接行列を隣接リストに変換します。 配列リスト
。 - 次に、頂点とその重みを保存するために、Pair クラスを作成します。
- 最も低い重みに基づいてリストを並べ替えます。
- 優先キューを作成し、最初の頂点とその重みをキューにプッシュします。
- 次に、エッジを通過し、最小の重みを変数に格納します。 年。
- 最後にすべての頂点を終えた後、ans を返します。
実装
C++
#include> using> namespace> std;> typedef> pair <> int> ,> int> >ぴー;>>' |
