LoginSignup
0
0

More than 3 years have passed since last update.

@ShibuKazu

クラスカルのアルゴリズム

Posted at

クラスカルのアルゴリズムとは

最小全域木を構成するためのアルゴリズム
Union-Findを用いて実装することが多い

なぜUnion-FInd?

Union-Findの以下の特性が最小全域木を構成する上で適している

  • 内部的に木構造で実装される
    →　一つの集合内部では連結性および閉路がないことが担保される
  • 一般的な実装の場合,同一の集合内部で結合は起こらない
    →　一般的な実装の場合、異なる祖先を持つグループ同士の結合を行うため
  • 一つのノードが複数の集合には属さない
    →　結合を行ったときに閉路ができないことが担保される

執筆途中

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0