2016-03-30 Prim法とKruskal法をPython 3で実装してみた:無向グラフの最小全域木を求めるアルゴリズム プログラミング グラフ理論 競技プログラミング Aizu Online Judge ふと思い立ち、Prim(プリム)法とKruskal(クラスカル)法をPython 3で実装しました。これらは無向グラフの最小全域木を求めるアルゴリズムであり、競技プログラミングでも用いられることがあるようです。この記事では、学習の記録を兼ねて、最小全域木や上記の手法の概略について述べてから、これらのアルゴリズムのPython 3による実装例を、Minimum Spanning Tree | Aizu Online Judgeの答案として示します。 続きを読む