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!


1 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|)$.

  • $\begingroup$ Thank you very much! $\endgroup$
    – DR_2001
    Jan 16 at 9:40

Your Answer

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

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