# How do Kruskal's and Prim's algorithms compare to each other?

I understand that both of them are used to find minimal spanning trees, and I've seen their implementations, but I don't understand how both of them compare to each other, and how they differ in complexity.

A tree in a graph is a connected acyclic subgraph. A spanning tree in a graph of order $$n$$ is a connected acyclic subgraph of order $$n$$ or equivalently a connected acyclic subgraph with $$n-1$$ edges.

Prim's algorithm consists of building a spanning tree by adding edges (and corresponding vertices), always keeping the connected and acyclic property, until the tree contains all vertices. The complexity of the algorithm is detailled here: it is $$O(|E|\log |V|)$$ with binary heaps, and $$O(|E| + |V|\log |V|)$$ (which is slightly better in general case) with Fibonacci heaps, a complicated data structure.

Kruskal's algorithm consists of building the spanning tree by adding edges always keeping the acyclic property, until there are $$|V|-1$$ edges. Its complexity is detailled there. It is $$O(|E|\log|V|)$$, but if the edges can be easily sorted, you can reach $$O(|E|\alpha(|V|))$$ with improved union-find data structure ($$\alpha(x)$$ is in practice very small, that is $$\leq 4$$ even if $$x$$ is the number of particles in the universe).

Both of them are greedy algorithms, but the property you keep invariant is not the same.

• Nice answer. However, the contrast seems misleading. Doesn't Prim's algorithm always keep the acyclic property as well? Aren't "until the tree contains all vertices" and "until there are |𝑉|−1 edges" exactly the same here? Apr 6, 2021 at 1:35
• Well yes, you are right about Prim (the converse would be problematic). About the "until" condition, I felt it was a bit different, since in Prim's algorithm, you add vertices to the tree you are constructing, but in Kruskal's algorithm, you start with a graph consisting of all vertices and no edges, so you only add edges (though that is maybe only my point of view). Apr 6, 2021 at 1:39
• "In Prim's algorithm, you add vertices ..." That is the point. To contrast with Kruskal's algorithm, we could describe Prim's algorithm as "building a spanning tree by adding vertices". Then "until the tree contains all vertices" sounds more smooth. Apr 6, 2021 at 1:48
• Kruskal requires sorting, so it requires $O(|E| \log |E|)$ time.
– user114966
Apr 6, 2021 at 4:08
• Thanks @Dmitry, I edited the answer. Apr 6, 2021 at 10:28