Given a weighted graph we can use kruskals algorithm to comp

Given a weighted graph, we can use kruskal\'s algorithm to compute its MST within theta(m log n) time, where m is the number of edges and n is the number of vertices. But consider a special case: there are only two possible weights for all the edges (e.g., the weight could be either 1 or 2), can we design a linear time (i.e., theta(n + m)) algorithm for MST? Consider a generalization of the above question 5: there are t greaterthanorequalto 2 possible weights for all the edges (e.g., the weight could be 1, 2, ..., t), and we assume t is a small constant. Can we design a linear time (i.e., theta(n + m)) algorithm for MST?

Solution

Use Prim\'s algorithm, Prim considers each edge once. The most costly part of Prim is where it looks for the next vertex to add. This is the vertex that has the cheapest connection to the tree from the remaining vertices. In case of two possible weights we only need to know if there are still vertices that have connection of weight 1 left because they have a priority over all the weight 2 edges.