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

Kruskal's Algorithm for Dense Graph
Автор aniervs, история, 5 лет назад, По-английски

Hello, how can Kruskal's algorithm be modified to run in O(n^2) time in a dense graph of n nodes??

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

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

This seems well explained and it has cpp code.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Why do you need Kruskal for such a task? Prim have your desired complexity, and is not much harder to implement compare to Kruskal.

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

    I am thinking that since Kruskal is usually faster to implement from scratch compared to Prim, the OP was hoping for an easy modification to Kruskal to achieve O(N^2) time complexity on dense graphs so that he could use it in more contexts during contests.

    → Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

It's the same as O(V^2 + E) dijkstra, just linearly search for smallest cost vertex that hasn't been visited yet.

Edit: I meant prim

→ Ответить