2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ A few remarks: If $G$ is a finite graph, the range of a function on the edges is automatically a finite set, do you mean that the size of the set is bounded by a constant? The complexity $O(|E|\alpha(|V|))$ is linear for all practical purposes. (I suppose this means that the purpose here is not practical, then) Finally, I don't think a purely linear deterministic minimum spanning tree algorithm is known for a bounded amount of weights. $\endgroup$ – Discrete lizard Feb 27 '17 at 20:14
  • $\begingroup$ @Discretelizard I have edited my question, you were right that my question wasn't so clear. $\endgroup$ – Don Fanucci Mar 1 '17 at 7:16
  • $\begingroup$ I think you should spend more time on this problem. OK, so adapting Kruskal's algorithm doesn't seem to work for this problem. So what other algorithms do you know for the minimum spanning tree problem? Have you tried adapting them to see if they can be adapted to meet your needs? Spend some time on each one, then edit your question to show what approaches you've tried for each standard MST algorithm. $\endgroup$ – D.W. Mar 1 '17 at 17:30
1
$\begingroup$

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.

  1. Create $R$ as an empty list of edges.
  2. Mark all vertices as unvisited.
  3. Create $k$ empty lists of edges $L_1, L_2, \cdots, L_k$.
  4. 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.
  5. Repeat the following steps until all $k$ lists are empty:
    1. Find the non-empty list with lowest subscript.
    2. Remove an element from the list just found. Name that element $e$.
    3. 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$.
  6. 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.

$\endgroup$
  • 1
    $\begingroup$ Wouldn't it be better if the answer simply described the priority queue and provided a complexity analysis of the way Prim's algorithm uses it instead of repeating some of the inner details of Prim's algorithm? I assume OP is familiar with Prim, so this seems superfluous $\endgroup$ – Dean Gurvitz Nov 2 '18 at 19:31
  • $\begingroup$ @DeanGurvitz Yes, you are right. This answer could be summarized in one sentence, just using Prim's algorithm but with its priority queue implemented as $|F|$ queues of equal-weight edges, assuming $|F|$ is a constant. I will update my answer. $\endgroup$ – Apass.Jack Nov 2 '18 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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