Implementation (Part 2)
Coddyの「プリム法 - グラフアルゴリズム」コースのレッスン 6/9。
常に最小コストの交差エッジを追加しながら、木を成長させます。
チャレンジ
中級それでは、木全体を成長させましょう。
連結グラフの頂点数 n とフラットな edges 配列（3つ組、無向）を受け取り、頂点 0 から木を開始して、最小全域木（Minimum Spanning Tree）の合計重みを返す prim という名前の関数を作成してください。
各頂点に対して inTree フラグを保持します。各ラウンドで、端点のうちちょうど1つが木に含まれている最もコストの低い辺を探し、その重みを加算して、木の外側にある端点を木に取り込みます。
自分で試してみよう
#include <stdlib.h>
int prim(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