VietCT's blog

Can implement Prim's algo in O(nlogn) ?
By VietCT, history, 6 years ago, In English

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

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +16 Vote: I do not like it

    You're right, iam solving problem which the vertices are points on 2d-plane. You have any link about this ?. Tkx.

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      Vote: I like it +42 Vote: I do not like it

      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...

      → Reply