1
$\begingroup$

Given a grid graph $G=(V,E)$ which has only two different integer costs/weights of 1 and 2. Find Minimum Spanning Tree in $O(|V|+|E|)$.

I tried the following:

  • Changing Kruskal using a counting Sort in $O(|E|)$. But can I say that this results in O(|E|+|V|)? Since Kruskal would normally be ${\displaystyle O(T_{sort}(|E|)+|E|\cdot \alpha (|V|))} =O(|E|)$ when $\alpha (|V|) \in O(1)$ Can this be stated for this case? I lack detailed understanding of inverse ackerman behaviour.
  • Other possibility changing Prim so that I use a priority queue which support del_min, decreaseKey and insert in $O(1)$. I thought about using two simple stacks or queues and only del_min from the one, which holds the 1 integers, but descreaseKey seems not efficient since I have to loop through the lists to find the elements. So maybe combine this with some kind so hash mapping to directly access each element in $O(1)$ for decreaseKey?

Both seem really close to the actual result, though I am struggling to see the right solution for this case.

$\endgroup$
2
2
$\begingroup$

Let $n=|V|$ and $m=|E|$.

Intuitively you want the to return the union of the edges in 1) a maximal spanning forest $F$ of the graph induced by the edges of weight $1$, with 2) a maximal spanning forest $F'$ of the graph obtained by identifying the edges of each tree in $F$ into a single vertex (where each edge in $F'$ actually represents an edge of $G$).

Some care is required to attain a running time of $O(n)$. The details are as follows.


Let $G_1$ be subgraph of $G$ induced by the edges of weight $1$. Let $C_1, \dots, C_k$ be the connected components of $G_1$. For each $C_i$, compute any a spanning tree $T_i = (V_i, E_i)$ of $C_i$. This requires $O(m)=O(n)$ time in total.

For each edge $e=(u,v)$ of weight $2$ in $G$ let $i$ and $j$ be such that $u \in C_i$ and $v \in C_j$. Let $k(e) = (\min\{i,j\}, \max\{i,j\})$. Sort the edges of $G$ in nondecresing order of $k(\cdot)$, keep at most one edge for each value of $k(\cdot)$. Let $S$ the resulting ordered set of edges. Notice that $S$ can be found in time $O(m)=O(n)$ using radix-sort.

Create a graph $G_2$ with vertex set $\{1, \dots, k\}$ and edge set $\{ k(e) : e \in S \}$. For an edge $(i,j)$ in $G_2$ let $\ell(i,j)$ be and edge $e$ in $G$ such that $k(e) = (i,j)$. This label $\ell(i,j)$ can be stored along with the edge $(i,j)$ itself, so that given $(i,j)$ we can find $\ell(i,j)$ in $O(1)$ time. This step also requires $O(n)$ time.

Finally, compute any spanning tree $T' = (V', E')$ of $G_2$. An MST of $G$ is the tree induced by the edges in $\left( \bigcup_{i=1}^k E_i \right) \cup \{ \ell(i,j) \mid (i,j) \in E'\}$.

Overall, the whole algorithm takes $O(n)$ time. The same algorithm extends naturally to any constant number of distinct edge weights.

Here is a visualization of the algorithm on the graph you proposed in the comments. Blue edges has weight $1$, red edges have weight $2$. The connected components of $G_1$ are highlighted in gray (and each connected component will be represented by a vertex in $G_2$). In this particular example $S$ contains all red edges of $G$ since each red edge connects a different (unordered) pair of connected components in $G_1$.

example

$\endgroup$
7
  • $\begingroup$ @JohnL. Sorry for not defining $n$ and $m$. I edited the answer. $m=\Theta(n)$ since, for $n>1$, the degree of each node is lower bounded by $1$ and upper bounded by $4$ (the input graph is a grid graph). $\endgroup$
    – Steven
    Feb 14 at 10:41
  • $\begingroup$ something I don´t understand about this procedure yet: given a $C_i, C_j$ so that we need at least two edges with the weight 2 to connect $C_i$ with $C_j$, it seems as if there wouldn´t be an edge within $k[]$ since it only holds edges which connect two different components with one edge or am I overlooking something? Another thing what is the label $\ell(i,j)$ used for? Is the step of computing the final MST something like looking at every edge and deciding whether it is in any $C_i$ or labeled with $\ell(i,j)$? $\endgroup$ Feb 14 at 13:37
  • $\begingroup$ I didn't fully understand your comment, but why do you say that you need 2 edges of weight 2 to connect $C_i$ with $C_j$? Exactly one edge is needed (you cannot have more edges as otherwise you'd be creating a cycle). The label $\ell(i,j)$ is there just because, formally, $G_2$ is a completely different graph than $G$. $\ell(i,j)$ is telling you any edge of $G$ that can be used to connect $C_i$ and $C_j$. In the final step you just take all the edges in any $T_i$ (not $C_i$!) plus an arbitrary edge $e$ between $C_i$ and $C_j$ for each edge $(i,j)$ in $T'$. This edge $e$ is exactly $\ell(i,j)$. $\endgroup$
    – Steven
    Feb 14 at 13:45
  • 1
    $\begingroup$ $k$ does not hold any edge, it is just a key used to get the sorted vector $S$ and to efficiently get rid of multiple edges between the same pair of components. $S$ contains edges. I think the misunderstanding here is that in your example graph $G_1$ contains 17 connected components. Namely, the whole first row, the whole last row, and one connected component for each vertex $g[i][j]$ with $i=2,3,4$ and $j=1,2,3,4,5$. Then $S$ contains all but $8$ edges of $G$. The $8$ missing edges are those in the first and last row. I've added a picture to my answer using your suggested graph as an example. $\endgroup$
    – Steven
    Feb 14 at 14:45
  • 1
    $\begingroup$ Do you mean a graph in which edge weights are non-negative integers and are upper bounded by some constant $c$? If so, yes. The same approach gives you a $O(m+n)$-time algorithm. For each $i=0, \dots, c$, consider the graph that contains only edges of weight $i$ and in which all vertices in the same connected component of the graph induced by the edges of weight $<i$ are identified in single vertex. Let $E_i$ be the edges in any maximal (w.r.t. the number of edges) spanning forest of this graph. The MST of your input graph is induced by the edges in $\cup_i E_i$. $\endgroup$
    – Steven
    Feb 14 at 15:33

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.