最小全域木 (Minimum Spanning Tree)
グラフの全頂点を連結したまま辺の重み総和を最小化する木。連結性を保ちつつ冗長な辺を取り除く基本手法で、本ヴォルトでは stella のダンジョン生成における部屋接続（リージョン間グラフから余分な通路を除去）など実応用に用いられている。
アルゴリズム
- 無向グラフ
- Kruskal法 — 辺を重み昇順にソートし、閉路を作らない辺を Union-Find で貪欲に採用する
- Prim法 — 1頂点から始め、最小の隣接辺を逐次取り込む
- 有向グラフ
- Edmonds’ algorithm (Chu-Liu/Edmonds) — 有向グラフの最小全域有向木を求める。クラスカル法やプリム法を有向グラフに使っても有向木にならない（全域木にすらならない場合がある）ため専用アルゴリズムが必要
注意点
- 無向グラフの直感をそのまま有向グラフへ持ち込めない点が落とし穴。out-degree や強連結性を意識した別アルゴリズムが要る。