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

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.

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

• Thank you very much! Jan 16 at 9:40