Minimum Spanning Tree

• 無向グラフ
  • Kruscal法
  • prim法
• 有向グラフ
  • Edmonds’ algorithm

参考文献

• 2022-09-03 有向木と有向全域木について調べて知ったこと。 - Qiita

無向グラフの最小全域木を求めるアルゴリズムといえばクラスカル法やプリム法が有名である。
しかしこれらのアルゴリズムを有向グラフに使ってみても、結果は有向木にはならない（それどころか全域木にならないかもしれない）。