この記事では、クラスカルのアルゴリズムについて説明します。ここでは、クラスカルのアルゴリズムの複雑さ、動作、例、実装についても説明します。
ただし、アルゴリズムに直接進む前に、まずスパニング ツリーや最小スパニング ツリーなどの基本用語を理解する必要があります。
スパニングツリー - スパニング ツリーは、無向接続グラフのサブグラフです。
最小スパニングツリー - 最小スパニング ツリーは、エッジの重みの合計が最小となるスパニング ツリーとして定義できます。スパニング ツリーの重みは、スパニング ツリーのエッジに与えられた重みの合計です。
さて、本題に入ります。
データ構造内の構造
クラスカルのアルゴリズム 接続された重み付きグラフの最小スパニング ツリーを見つけるために使用されます。このアルゴリズムの主な目標は、グラフのすべての頂点を横断できるエッジのサブセットを見つけることです。これは、全体的な最適化に焦点を当てるのではなく、あらゆる段階で最適な解決策を見つける貪欲なアプローチに従います。
クラスカルのアルゴリズムはどのように機能するのでしょうか?
Kruskal のアルゴリズムでは、重みが最も低いエッジから開始して、目標に到達するまでエッジを追加し続けます。 Kruskal のアルゴリズムを実装する手順は次のとおりです。
- まず、すべてのエッジを低重みから高重みまでソートします。
- ここで、重みが最も低いエッジを選択し、それをスパニング ツリーに追加します。追加するエッジが循環を作成する場合は、そのエッジを拒否します。
- すべての頂点に達するまでエッジを追加し続け、最小スパニング ツリーが作成されます。
クラスカルのアルゴリズムの応用例は次のとおりです。
- クラスカルのアルゴリズムは、都市間の電気配線のレイアウトに使用できます。
- LAN接続の敷設に使用できます。
クラスカルのアルゴリズムの例
ここで、例を使用して Kruskal のアルゴリズムの動作を見てみましょう。例を使用すると、Kruskal のアルゴリズムを理解しやすくなります。
アメリカ合衆国には都市がいくつありますか
重み付けされたグラフが - であると仮定します。
上のグラフのエッジの重みを以下の表に示します。
Javaの同等のインターフェース
| 角 | AB | 交流 | 広告 | しかし | 紀元前 | CD | の |
| 重さ | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
次に、上で指定したエッジを重みの昇順に並べ替えます。
| 角 | AB | の | 紀元前 | CD | しかし | 交流 | 広告 |
| 重さ | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
それでは、最小スパニングツリーの構築を始めましょう。
ステップ1 - まずエッジを追加します AB 重さで 1 MSTへ。
ステップ2 - エッジを追加する の 重さで 2 サイクルを作成していないため、MST に送信されます。
ステップ 3 - エッジを追加する 紀元前 重さで 3 サイクルやループを作成しないため、MST に送信されます。
ステップ4 - さあ、エッジを選んでください CD 重さで 4 サイクルを形成していないため、MST に転送されます。
部分的な依存関係
ステップ5 - その後、エッジを選択します しかし 重さで 5. このエッジを含めるとサイクルが作成されるため、破棄します。
ステップ6 - 端を選ぶ 交流 重さで 7。 このエッジを含めるとサイクルが作成されるため、破棄します。
ステップ7 - 端を選ぶ 広告 重さで 10. このエッジを含めるとサイクルも作成されるため、破棄します。
したがって、クラスカルのアルゴリズムを使用して、指定された重み付きグラフから得られる最終的な最小スパニング ツリーは次のようになります。
npmインストールコマンド
MST のコストは、= AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10 となります。
ここで、上記のツリーのエッジの数は、頂点の数から 1 を引いたものに等しくなります。したがって、アルゴリズムはここで停止します。
アルゴリズム
Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END
クラスカルのアルゴリズムの複雑さ
ここで、クラスカルのアルゴリズムの時間計算量を見てみましょう。
クラスカルのアルゴリズムの時間計算量は O(E logE) または O(V logV) で、E は番号です。 V はエッジの番号です。頂点の。
クラスカルのアルゴリズムの実装
次に、kruskal のアルゴリズムの実装を見てみましょう。
プログラム： C++ で kruskal のアルゴリズムを実装するプログラムを作成します。
#include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes >> edges; for(int i = 0;i <edges;++i) { cout<> x >> y >> weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout <<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>