Блог пользователя VietCT

Can implement Prim's algo in O(nlogn) ?
Автор VietCT, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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...

      → Ответить