Prim のアルゴリズムとその実装方法を知っています。また、その時間計算量が O(E + V log(V)) である理由も認識しています。
エッジを E 回 (つまり O(E) で) 追加し、最小の V 回 (つまり O(V*log(V)) を選択します。しかし、私はその一部を理解していません: なぜ V 回?! 私は知っていますツリーには V-1 エッジがありますが、最も重いエッジが MST にある必要がある場合は、V 時間ではなく、最小の E 時間を選択する必要があります。
例: 各エッジの重みが 1 の完全なグラフ。ただし、接続されているすべてのエッジの重みが 10^18 である 1 つの頂点を除きます。