MST for a finite number of weights

Let $F$ be a finite set of real numbers say $\{w_1,\dots,w_k\}$.

Let $G=(V,E)$ be an undirected connected graph and let $w\colon E\to F$ be a weight function.

Describe a linear time algorithm that will find a Minimum spanning tree in $G$.

Assume that $|V|\gg k$, i.e. the number of vertices is much larger than k.

I know that in such a case we can sort the edges in linear time and then use Kruskal's algorithm, but that will be slightly worse than linear time — $O(|E|\alpha(|V|))$.

I have heard about an approach that uses $|F|$ queue's but I couldn't figure it out, please help.

Summary: An algorithm of linear time in $|E|$ can be given by an implementation of Prim's algorithm where its priority queue is $|F|$ queues of equal-weight edges, assuming $|F|$ is a constant.

We will explicitly let $k=|F|$ be a constant. This constantness is indicated by "in such a case we can sort the edges in linear time.". It is then superfluous to "assume that |V|>>k, i.e. the number of vertices is much larger than k", since the complexity analysis by the big $O$-notations is about the behaviour of the algorithm when the input size increases to infinity, skipping the cases when the input size is not big enough.

Let us sort $F$ by constant time. To each edge with weight $w$ that is the $i$-th smallest in $F$ for some $1\le i\le k$, we will reassign weight $i$. Since comparison compatible weights of edges will lead to the same set of MSTs, this weight reassignment, which is done in linear time of $|E|$, does not affect the correctness of all later arguments. So, we will assume, furthermore, $F=\{1, 2, \cdots, k\}$. (We can, alternatively, add this step to the algorithm below.)

Here is the description of a wanted algorithm in detail (given an undirected connected graph $G=(V,E)$ and a weight function $w:E→F=\{1, 2, \cdots, k\}$). For brevity let us call the algorithm Prim's algorithm with constant queues (PAWCQ). PAWCQ is, most probably, more or less the "approach that uses $|F|$ queues" that is mentioned by the OP.

• Create $R$ as an empty list of edges.

• Mark all vertices as unvisited.

• Create $k$ empty lists of edges $L_1, L_2, \cdots, L_k$.

• Select an arbitrary vertex $v_0$. Iterate through all edges incident to $v_0$, putting an edge in $L_i$ if its weight is $i$. Mark $v_0$ as visited.

• Repeat the following steps until all $k$ lists are empty:

• Find the non-empty list with lowest subscript.

• Remove an element from the list just found. Name that element $e$.

• If both vertices of $e$ are marked visited, do nothing. Otherwise, let $u$ be the vertex marked unvisited. (The other vertex must be marked visited). Iterate through all edges incident to $u$, putting an edge in $L_i$ if its weight is $i$. Mark $u$ as visited. Add $e$ to $R$.

• return $R$.

We can see that PAWCQ is indeed a variation of Prim's algorithm. In particular, it will always terminate in finitely many steps to return an MST of $G$.

The time complexity of PAWCQ is asymptotically linear in $|E|$ when $G$ is given by its adjacency list (in the usual computation models), since both the insertion of an edge into the constant queues and the removal of an edge from the contant queues take constant time and each edge is inserted once and removed once.

Note that the order in which we remove an element in step $5.2$ does not affect the correctness of the algorithm. We can implement each list as, for example, a FIFO queue or a FILO stack.

Note that we can speedup the algorithm in several places for better performance, such as ending the algorithm as soon as we have collected $|V|-1$ edges. However, none of them will improve the big $O$ complexity since $O(|E|)$ is the best possible.

StackExchange Computer Science Q#70917, answer score: 2