Implementation (Part 2)
Coddyの「クラスカル法 - グラフアルゴリズム」コースのレッスン 6/9。
MSTが完成するまで、最も安価な安全なエッジを追加します。
チャレンジ
中級それでは、MST（最小全域木）を構築しましょう。
n と、連結グラフのフラットな edges 配列（3つの値のセット、無向）を引数に取る、kruskal という名前の関数を作成し、その最小全域木の合計重みを返してください。
未使用のエッジの中で最もコストが低いものを繰り返し取り出します。その端点が異なる集合にある場合は、それらを結合（union）して重みを加算し、そうでなければスキップします。
前のレッスンの union-find の考え方を再利用してください。
自分で試してみよう
#include <stdlib.h>
int kruskal(int n, int* edges, int edges_size) {
// ここにコードを記述してください
return 0;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
クラスカル法 - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity