aniervs's blog

Kruskal's Algorithm for Dense Graph
By aniervs, history, 7 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?
»
7 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

This seems well explained and it has cpp code.

→ Reply
»
7 years ago, hide # |
 
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
»
7 years ago, hide # |
← 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