Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$

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

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$$. • @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). Feb 14 '21 at 10:41
• 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)$? Feb 14 '21 at 13:37
• 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)$. Feb 14 '21 at 13:45
• $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. Feb 14 '21 at 14:45
• 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$. Feb 14 '21 at 15:33