ITエンジニアのための転職・就職支援サービスである「paiza」が提供している、プログラミング教育コンテンツ「paizaラーニング」中の「レベルアップ問題集」に「Union-find・クラスカル法メニュー」というのがある。
「クラスカル法」というのは、グラフ・ネットワーク系の問題である「最小全域木問題」を解くためのアルゴリズムの1つで、「最小全域木」なんて専門用語を見るとビビッちゃうけれども、やっていること自体は意外と簡単。クラスカル法そのものよりも、クラスカル法で用いる「ユニオンファインド」というアルゴリズムの方が少し難しい。
「クラスカル法はユニオンファインドを用いる」と言うよりも、「ユニオンファインドを利用して最小全域木問題を解くアルゴリズムがクラスカル法である」という感じかな。より基礎的なアルゴリズムである「ユニオンファインド」の方が大事かも。
考えてみれば、同じくグラフ・ネットワーク系の問題である「最短経路問題」を解くためのアルゴリズムの1つである「ダイクストラ法」も、やっていることそのものは意外と単純で、ダイクストラ法そのものよりもダイクストラ法がその内部で用いる「優先度付きキュー（プライオリティーキュー）」の方が難しいし、大事かもしれない。より基礎的なものを理解することの方が重要なのだ（その「優先度付きキュー」も、これまた内部的に用いている「ヒープ」を理解することの方が大事だと思う）。
ダイクストラ法も、「ダイクストラ法は優先度付きキューを用いる」と言うよりも「優先度付きキューを利用して最短経路問題を解くアルゴリズムがダイクストラ法である」と言った方が僕にはシックリくるので、そういうところが「クラスカル法」と「似た者同士」だなぁ、と感じる。
もっとも、それを言ったら、「クラスカル法」よりも「プリム法」の方が「ダイクストラ法」にもっと似てるかな（「プリム法」は、「優先度付きキュー」を用いて「最小全域木問題」を解くアルゴリズム）。
