Kruskal's Algorithm: Difference between revisions

From Rice Wiki
No edit summary
Line 15: Line 15:


For weighted disjoint set, checking cycle takes log V, and adding edge takes log V
For weighted disjoint set, checking cycle takes log V, and adding edge takes log V
For fast-find, where all members have the same ID, fast-set-id needs O(1) and union needs O(n)

Revision as of 00:02, 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

For fast-find, where all members have the same ID, fast-set-id needs O(1) and union needs O(n)