Kruskal法をココロから納得する - けんちょんの競プロ精進記録僕は、最小全域木を求めるKruskal法をココロから納得するのにとても長い時間が掛かってしまいました。本記事では、備忘録的な目的を兼ねて、少しKruskal法について書いてみたいと思います。 僕は、Kruskal法は今年5月頃初めて知ったのですが、そのときはどうしてコレで最小全域木が求まるのか、不思議でなりませんでした。その後6月頃にアルゴリズムイントロダクションを読んで、ひとまず証明は理解したのですが、イマイチなかなかイメージが掴めませんでした。さらに7月にはマトロイドの触りを勉強し、マトロイドのGreedyアルゴリズムからKruskal法が自然に導かれることを学んだのですが、それでもまだKruskal法をココロから納得するには至れませんでした。 それくらい、Kruskal法を納得するのにとても苦労しました。ようやく自分なりにKruskal法が納得できるようになったのは、マトロイドの交換
