Как вы, возможно, уже знаете,
Prim хорош для плотных графов, а Kruskal хорош для разреженных.
В Kruskal сложность алгоритма определяется сортировкой ребер.
Так что это большой O * O(E log E) в обычных случаях с нормальными эффективными сортировками.
С Prim сложность аналогична алгоритму Дейкстры. (Вы можете легко модифицировать код Dijkstra в Prim)
Так что это похоже на O((V+E) log(V)) с приоритетной очередью (кучей).
Так что, когда График разрежен (E < V), Kruskal O(E log E) и Prim O(V log V), поэтому Круслак выигрывает.
А когда График плотный (E is close to V^2-1), Prim O(V^2 log V^2) и Prim O(V^2 log V), поэтому Prim выигрывает.
Но в большинстве случаев вы можете использовать оба алгоритма без заметных отличий.