グラフ理論一覧

NO IMAGE

[グラフ] プリム法

プリム法はクラスカル法と同じ最小全域木を探すアルゴリズムです。 最短経路を探すダイクストラ法にとても良く似ています。 プリム法 プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木(対象とな...

NO IMAGE

[グラフ] クラスカル法

クラスカル法は、素集合データ構造を使い最小全域木の問題を解くアルゴリズムです。 全域木 ある無向グラフを考えた時、このグラフの全域木とは、グラフの頂点全てを使い構成される部分グラフで、木構造になるものです。 全域木(ぜんいきぎ、英:Span...