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

Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | Um_nik | 3535 |

4 | 300iq | 3317 |

5 | ecnerwala | 3294 |

6 | maroonrk | 3268 |

7 | TLE | 3223 |

8 | scott_wu | 3209 |

9 | WZYYN | 3180 |

10 | boboniu | 3174 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 197 |

2 | antontrygubO_o | 187 |

3 | pikmike | 182 |

3 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 168 |

7 | Um_nik | 164 |

8 | tourist | 163 |

8 | Monogon | 163 |

10 | McDic | 162 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/09/2020 01:00:02 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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

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:

Of course, finding the delaunay triangulation is an enormous amount of work to actually implement...