想請問各位
kruskal跟prime的資料結構若是改用adjacency matrix的話
他們各自的時間複雜度會跟使用list的時候有差嗎？
我有自己大概先想了一下 能幫我看一下哪邊有誤嗎
Kruskal
每個頂點都做make-set：Ｏ(V)
bottom up建heap：Ｏ(V^2) //邊總數E改為V^2
由小到大取出每個邊+調整：Ｏ(V^2*logV^2) = Ｏ(V^2*logV) //邊總數E改為V^2
total time：Ｏ(V^2*logV)
Prim
每個頂點的距離初始化：Ｏ(V)
建fibonacci heap：Ｏ(V)
由小到大取出每個頂點v：Ｏ(V*logV)
比較每個相鄰於v的頂點距離並調整(=比較每個邊)：Ｏ(V^2)
total time：Ｏ(V^2)
想請問大家這樣子想是正確的嗎？先謝謝大家了