想请问各位
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)
想请问大家这样子想是正确的吗？先谢谢大家了