DOSEIの日記

技術メモ+日常ログ

○最小重み全域木を求めるアルゴリズム(クルスカルのアルゴリズム

  1. 最小の重みの辺を登録
  2. まだ登録されていない辺から、サイクルにならないような最小の重みを登録
  3. 全域木でなければ、2へ

このような各段階で最適なものを選ぶ方法を貧欲法(Greedy Algorithm)という。
サイクルになるかどうかの判定方法。

  • 両端が無印なら、新しい番号の同じラベルを両側につける。
  • 片側のみラベルがある場合は、同じラベルをもう一方につける。
  • 両端が異なる場合は、どちらか一方のラベル群をもう一方に書き換える。同じ時はサイクルになるので×

○グラフの頂点探索

○最短経路問題
ダイクストラ

…適当