对于用于STL优先级队列优化的prim算法和使用c ++排序的kruskal算法,哪种类型的图适合这两种算法?
发布于 2020-04-14 15:49:36
你可能已经知道了,
Prim适用于密集图,Kruskal适用于稀疏图。
对于Kruskal,算法的复杂性主要取决于对边的排序。
因此,在一般情况下,它的大O是O(E log E),具有正常的有效排序。
使用Prim,其复杂度与Dijkstra的算法相似。(您可以轻松地将Dijkstra代码修改为Prim )
因此,它类似于具有优先级队列(堆)的O((V+E) log(V))。
因此,当图是稀疏的(E < V)时,Kruskal是O(E log E),Prim是O(V log V),所以Kruslak赢了。
当图是密集的(E is close to V^2-1)时,Prim是O(V^2 log V^2),Prim是O(V^2 log V),所以Prim获胜。
但在大多数情况下,您可以同时使用这两种算法,而没有明显的差异。
https://stackoverflow.com/questions/60144343
复制相似问题