Find MST with bounded edge weight in O(|V|+|E|)

Question

I need to describe (even in words) an algorithm that gets a connected, undirected, weighted graph so that the weight of each edge is either 1,2 or 3; and returns MST of that graph is time complexity O(|V|+|E|).

I thought to take kruskal algorithm and change the sorting algorithm to be counting sort (O(|E|) instead of comparison based sort (O|ElogE|) however this doesn't give well enough time complexity because of the "cost" of the set data-stracture (makeset,findset,union). Maybe some modification of the Prim's algorithm can work although I can't think of anything.

I'd love to get some help with this; I am struggling to find anything that would work in the required time complexity.

Thank you in advance!

Answer 1

You should use Prim's algorithm instead of Kruskal's algorithm.

Given a weighted undirected graph $G = (V, E, f)$ with $f(E) \subseteq \{1, 2, 3\}$ as an adjacency lists array, the following should work:

• Let $W$ be a boolean array of length $n = |V|$, with all values set to false, except $W[0]$ set to true.
• Let $T$ be a graph (as an adjacency lists array) with $n$ vertices and no edge.
• Let $E_1$ (resp. $E_2$ and $E_3$) be the sets (or linked lists, as your prefer) of edges incident to the vertex $0$ of weight $1$ (resp. 2 and 3).
• While $T$ has less than $n-1$ edges:
  • pick $\{u, v\}$ an edge in $E_1$ or $E_2$ or $E_3$ in this order, stopping with the first non empty set;
  • assume WLOG that $W[u]$ is true. If $\neg W[v]$ then:
    • add $\{u, v\}$ to $T$;
    • $W[v]\leftarrow $ true;
    • add to $E_1$ (resp. $E_2$ and $E_3$) all edges incident to the vertex $v$ of weight $1$ (resp. 2 and 3).

This is exactly Prim's algorithm, but the extraction of the minimum weight edge is done using $E_1$, $E_2$ and $E_3$, so it is done in constant time. Each edge is added and extracted from $E_i$ sets at most twice (one for each of its extremities). If an edge $\{u, v\}$ such that $W[u] \land W[v]$ is extracted, it is just ignored. All other operations in the loop are in constant time, so the overall complexity is indeed in $\mathcal{O}(|V| + |E|)$.