# graphs – How do Kruskal’s and Prim’s algorithms compare to each other?

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 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. 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.

Posted on Categories Articles