Prim算法的最壞情況圖

Question

我的算法類正在討論Prim算法，作爲查找加權圖的最小生成樹的方法。我們的教授讓我們試着想一個Prim算法需要N^2次解決的圖的例子（N =頂點數）。班上沒有人能夠想到他們的頭頂，所以我問你。我很確定Prim的算法= O（N^2），所以這將是算法的最壞情況。

什麼是Prim算法需要N^2個時間才能解決的圖的一個很好的例子？

Answer 1

如果我正確理解你的問題，這個例子是微不足道的。

如果圖形完整，則有O(N^2)邊緣，因此只需讀取圖形即可獲得O(N^2)。