1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – John L.
    Apr 6, 2021 at 1:35
  • $\begingroup$ 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). $\endgroup$
    – Nathaniel
    Apr 6, 2021 at 1:39
  • $\begingroup$ "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. $\endgroup$
    – John L.
    Apr 6, 2021 at 1:48
  • 1
    $\begingroup$ Kruskal requires sorting, so it requires $O(|E| \log |E|)$ time. $\endgroup$
    – user114966
    Apr 6, 2021 at 4:08
  • $\begingroup$ Thanks @Dmitry, I edited the answer. $\endgroup$
    – Nathaniel
    Apr 6, 2021 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.