Kruskal's Algorithm: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Infobox Algorithm|runtime=Sort + E cycle? + (V - 1) adding-edge}} | {{Infobox Algorithm|runtime=Sort + E cycle? + (V - 1) adding-edge|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked"> | ||
== Kruskal's Algorithm == | |||
</aside><span></span> | |||
= Approach = | = Approach = | ||
Revision as of 00:00, 13 March 2024
<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">
Kruskal's Algorithm
</aside>
Approach
Select edges in order of smallest to largest, using disjoint-sets to prevent cycles.
Analysis
Sort edges + E (cycle?) + (V - 1) adding edge
Sorting takes E log E
For weighted disjoint set, checking cycle takes log V, and adding edge takes log V
