Kruskal's Algorithm: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
| Line 14: | Line 14: | ||
For fast-find, where all members have the same ID, fast-set-id needs O(1) and union needs O(n) | For fast-find, where all members have the same ID, fast-set-id needs O(1) and union needs O(n) | ||
[[Category:Algorithms]] | |||
Revision as of 00:06, 13 March 2024
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)
