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.

Alternatively use Prim's algorithm. No need to keep track of components. Prim considers each edge once (assuming adjacency-lists). The most costly part of Prim is looking for the next vertex to add: the one of the remaining vertices that has the cheapest connection to the tree already constructed. Here we only have to know whether there are still vertices that have a connection of weight 1 (because they have priority to those of weight 2). I would say that a single list can handle this.

I also think that there might be another approach. Start building spanning trees for the components when we only use edges of weight 1, just ignoring edges of weight 2. Then the components are "big vertices" that can be connected by a tree using the remaining edges of weight 2. Keeping components here is easy: all vertices reached in a new component are labelled with the same number. That number identifies the "big vertex".

StackExchange Computer Science Q#28635, answer score: 6