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

ignougroup
Problem Detail: 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.

Asked By : TheNotMe

Answered By : lPlant

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|)$
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28635