最小木(minimum spanning tree,最小極大木とも)

• 重みつきグラフにおいて、すべてのノードを結ぶエッジの集合で、辺の重みの総和が最小のもの
• 疎グラフの場合
  
  • 大きくわけてアプローチは２つ
    
    • １つのノードからスタートし、そのノードを含む木を成長させ、すべてのノードが結ばれるまで続ける(順位優先探索、ステップ)
    • すべてのノードからスタートし、それぞれのノードを個別の木としてとらえ、それらをつないで行き、すべてのノードがつながるまで続ける(クラスカル法、ステップ)
  • まだ整理できていない疑問
    
    • 今、連結なグラフが与えられており、そのノード集合を複数の部分集合に分割し、部分集合同士には共通のノードが存在しないときに、その部分集合の最小木を作成するとする。複数の最小木ができるが、その最小木に共通して含まれるエッジと、ある最小木に特異的に含まれるエッジと、いずれの最小木にも含まれないエッジとでは、どういう意味があるのだろうか？
• 密グラフの場合
  
  • 全ノードについて優先度値を与え、その優先度リストの更新と優先度の最小値を見つけるループによる(プリム)