Primのアルゴリズムのワーストケースグラフ

Question

My Algorithmsクラスは、加重グラフの最小スパニングツリーを見つける方法として、Primのアルゴリズムについて説明しています。私たちの教授は、Prim's Algorithmが解決するのにN^2時間かかる（N = Verticesの数）グラフの例を考えようとしました。クラスの誰も頭の上から外れていると考えることができないので、私はあなたに尋ねています。プリムのアルゴリズム= O（N^2）なので、これはアルゴリズムの最悪のシナリオです。

Primのアルゴリズムが解決するのにN^2時間かかるグラフの良い例は何ですか？

Answer 1

私があなたの質問を正しく理解していれば、その例は簡単です。

グラフが完成したら、O(N^2)のエッジがあるので、グラフを読み取るだけでO(N^2)となります。