グラフ-最小全域木(MST )-プリム法

最小全域木(MST - Minimum Spanning Tree)

用語 アルゴリズム 例題 用語用語を整理しておきます(蟻本p. 99-): 全域木:無向グラフの部分グラフで,任意の2頂点が連結である木. 最小全域木:辺のコストの和が最小の全域木. アルゴリズム プリム法:木$T$に,木$T$の頂点と木$T$に含まれない頂点を…