aniervs's blog

Kruskal's Algorithm for Dense Graph
By aniervs, history, 5 years ago, In English

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

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

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This seems well explained and it has cpp code.

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

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

    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.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply