2
$\begingroup$

G=(v,e) , with weight on the edges than can be only a or b (when $a

I need to find MST of the graph in O(v+e).

I think to put all the edges in array, and than scanning the array. first only check about a, and after about b. The algorithm is like Kruskal's: check about evey edge if it doesnt form a cycle. but I'm not sure that this is taking O(v+e).

Thank u!

1 Answers 1

1

The running time of the algorithm of Kruskal is dominated by the sorting time of the edges according to their weights. In your case you can do this in linear time. The rest of Kruskal's algorithm also runs in linear time. So you get linear running time after all.

  • 0
    @Akhil: Oh you are right... But I think I can fix it by not using Kruskal's algorithm :) I think two DFS runs should be enough. In the the first run you use only edges with the lower weight and build$a$maximal tree. If it is also a connected spanning tree you have the MST otherwise you fill up this tree with edges with higher weight to make it spanning and connected.2011-03-12