この記事では、プリムのアルゴリズムについて説明します。アルゴリズムとともに、prim のアルゴリズムの複雑さ、動作、例、実装についても見ていきます。
本題に入る前に、スパニング ツリーや最小スパニング ツリーなどの基本的かつ重要な用語について説明する必要があります。
スパニングツリー - スパニング ツリーは、無向接続グラフのサブグラフです。
最小スパニングツリー - 最小スパニング ツリーは、エッジの重みの合計が最小となるスパニング ツリーとして定義できます。スパニング ツリーの重みは、スパニング ツリーのエッジに与えられた重みの合計です。
さて、本題に入りましょう。
プリムのアルゴリズム は、グラフから最小スパニング ツリーを見つけるために使用される貪欲なアルゴリズムです。 Prim のアルゴリズムは、エッジの重みの合計が最小化されるように、グラフのすべての頂点を含むエッジのサブセットを見つけます。
Prim のアルゴリズムは単一ノードから開始し、すべてのステップですべての接続エッジを持つすべての隣接ノードを探索します。グラフ内でサイクルを引き起こさない最小の重みを持つエッジが選択されました。
プリムのアルゴリズムはどのように機能するのでしょうか?
Prim のアルゴリズムは、1 つの頂点から開始して、目標に到達するまで最小の重みを持つエッジを追加し続ける貪欲なアルゴリズムです。プリムのアルゴリズムを実装する手順は次のとおりです。
- まず、ランダムに選択された頂点で MST を初期化する必要があります。
- 次に、上記の手順でツリーと新しい頂点を接続するすべてのエッジを見つける必要があります。見つかったエッジから最小のエッジを選択し、ツリーに追加します。
- 最小スパニングツリーが形成されるまでステップ 2 を繰り返します。
prim のアルゴリズムの応用例は次のとおりです。
- Prim のアルゴリズムはネットワーク設計に使用できます。
- ネットワークサイクルを作るために使用できます。
- 電気配線ケーブルの敷設にも使用できます。
プリムのアルゴリズムの例
ここで、例を使用して prim のアルゴリズムの動作を見てみましょう。例を使用すると、プリムのアルゴリズムを理解しやすくなります。
加重グラフが次のようになると仮定します。
ステップ1 - まず、上のグラフから頂点を選択する必要があります。 Bを選択しましょう。
Javaメソッド
ステップ2 - ここで、頂点 B から最短のエッジを選択して追加する必要があります。頂点 B からは、重み 10 の B から C までのエッジと、重み 4 のエッジ B から D までの 2 つのエッジがあります。エッジのうち、エッジ BD の重みは最小です。 。したがって、それを MST に追加します。
ステップ 3 - ここで、もう一度、他のすべてのエッジの中で最小の重みを持つエッジを選択します。この場合、エッジＤＥおよびエッジＣＤがそのようなエッジである。それらを MST に追加し、C の隣接、つまり E と A を探索します。そこで、エッジ DE を選択して MST に追加します。
ステップ4 - ここで、エッジ CD を選択し、MST に追加します。
ステップ5 - 次に、エッジ CA を選択します。ここでは、グラフにサイクルが作成されるため、エッジ CE を選択することはできません。したがって、エッジ CA を選択して MST に追加します。
したがって、ステップ 5 で生成されたグラフは、指定されたグラフの最小スパニング ツリーになります。 MST のコストは次のとおりです。
MST のコスト = 4 + 2 + 1 + 3 = 10 ユニット。
アルゴリズム
Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT
Prim のアルゴリズムの複雑さ
ここで、Prim のアルゴリズムの時間計算量を見てみましょう。プリムのアルゴリズムの実行時間は、グラフのデータ構造の使用とエッジの順序によって異なります。以下の表にいくつかの選択肢を示します -
| 最小エッジ重みに使用されるデータ構造 | 時間計算量 |
|---|---|
| 隣接行列、線形探索 | O(|V|2) |
| 隣接リストとバイナリ ヒープ | O(|E| log |V|) |
| 隣接リストとフィボナッチヒープ | O(|E|+ |V| log |V|) |
Prim のアルゴリズムは、隣接行列または隣接リストのグラフ表現を使用することで簡単に実装でき、最小の重みを持つエッジを追加するには、重みの配列を線形に検索する必要があります。 O(|V| が必要です2） 実行時間。ヒープの実装を使用してアルゴリズムの内部ループで最小重みエッジを見つけることで、さらに改善できます。
プリムのアルゴリズムの時間計算量は O(E logV) または O(V logV) で、E は番号です。 V はエッジの番号です。頂点の。
Prim のアルゴリズムの実装
それでは、prim のアルゴリズムの実装を見てみましょう。
プログラム： C言語でprimのアルゴリズムを実装するプログラムを書きます。
#include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
weight
'); printf(' %d
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that's all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>