# Find an MST in a graph with edge weights from {1,2}

I've been asked the following question:

Given a connected undirected graph $G=(V,E)$ and a weight function $w: E \to \{1,2\}$, suggest an efficient algorithm that finds an MST of the graph.

After a few clarifications, the algorithm should run in time $O(|V|+|E|)$. I believe we can do this because of the fact that there are two types of weight of edges.

I tried the following idea, which did not work (I had a contradicting example):

Run BFS on the graph, and output the BFS tree.

I thought that shortest paths in this case would also mean easiest trees, but this is not the case.

I also tried to make each edge $e$ such that $w(e)=2$ into two edges of weight $1$ but my friend also gave a contradicting example.

Can you help please? This is not a homework question, this is a previous exam question as I am studying for my algorithms exam which is soon.

Since you have only 2 possible edge weights you can perform a linear time sort on the edges, then perform Kruskal's algorithm. The complexity of Kruskal's algorithm comes from its need to sort the edges in terms of weight, which previously had to be done in $O(ElogE)$ time, now however, you can sort the edges in linear time and then perform Kruskal's to complete the search. Creating the vertex set is $O(|V|)$ time, sort in $O(|E|)$ ,build MST in $O(|E|)$ total time is $O(|E|+ |V|)$
• Actually, it's slightly different, since a candidate edge $e=\{u,v\}$ might have endpoints that have already been visited. If $u$ and $v$ lie in the same component then $e$ would be rejected, but if they lie in different components then it would be permissible to include the edge in the MST. In other words, you'd need to flag vertices by which component their edge lay in. – Rick Decker Jul 22 '14 at 20:13