Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank u, but how I do it in linear time? It's ok to scan all the edegs&vertex 2 times, and checking each time about a & b? It's consider a linear time (in $O(|v|+|E|)$). The main problem is that I have to sort the edges, in purpose to know which edges I already scan. –  user8069 Mar 12 '11 at 6:43
    
I think it suffices to scan the edges only once. Every edge with weight $a$ put in a list $A$ and every edge with weight $b$ in list $B$. In the algorithm you start with the edges in $A$ (removing each edge you currently process) and if $A$ is empty go on with $B$. –  Marc Gillé Mar 12 '11 at 8:22
    
Dear Marc, are you sure this is correct? For instance, Kruskal's algorithm requires a disjoint-set data structure, which I believe requires $\Omega$ of an inverse Ackermann. –  Akhil Mathew Mar 12 '11 at 15:56
    
@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. –  Marc Gillé Mar 12 '11 at 17:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.