Help us understand the problem. What is going on with this article?

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

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

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

なぜUnion-FInd?

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

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

執筆途中

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away