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.