Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### VietCT's blog

By VietCT, history, 8 days ago, ,

I was wondering if we could implement Prim's algo in O(n log n) (n is number of vertices)

• +17

 » 8 days ago, # |   +11 I believe the the best we can get is $O(m\cdot\lg(n))$ for general graphs. I'm assuming the problem you are solving doesn't give you edges explicitly but instead defines their weight based on some vertex properties. Like $cost(u, v) = a_u \oplus a_v$(You can find this problem here). Or if a vertex is connected to a range a contiguous range of vertices. Or if the vertices are actually points on 2d-plane and we use euclidean distance.tl;dr; No, unless graph has special properties.
•  » » 8 days ago, # ^ | ← Rev. 2 →   +16 You're right, iam solving problem which the vertices are points on 2d-plane. You have any link about this ?. Tkx.
•  » » » 8 days ago, # ^ |   +42 If you are using euclidean distance on points on the plane, you know that the minimum spanning tree will be a subset of the delaunay triangulation, which has O(n) edges, and can be found in O(n*log(n)). So you can do this: Find the DT of the n points in n*log(n). Run normal kruskals on those ~9*n edges in m*log(n) = n*log(n) Of course, finding the delaunay triangulation is an enormous amount of work to actually implement...