全域木
各辺に重み(コスト)がある場合、最小の総和コストで構成される全域木を最小全域木という。
クラスカル法 - 単純な貪欲法で計算量は O ( E log  E ) {\displaystyle O(E\log {E})} 。
プリム法 - 貪欲法だが計算量は O ( E + V log  V ) {\displaystyle O(E+V\log {V})} 。辺の数が頂点に比べて十分大きいときは O ( E ) {\displaystyle O(E)} と見なせる。
辺の重みが均一の場合は幅優先探索で O ( E ) {\displaystyle O(E)} で求まる。