全域木

すべての頂点集合Vを持ち、辺集合Eの一部の集合で構成される木

どんなグラフも少なくとも1つは全域木をもつ

最小全域木

辺コストの総和が最小になる全域木

すべての頂点を探索する経路を見つける

辺のコストは考えない

前に進めない頂点に突き当たったら辺をさかのぼって前に進める頂点を探す

幅優先探索

待ち行列を使って横を順次攻めながら探索する

コストは考えない

最良優先探索

接続辺のコストが最小のものを選ぶ