Kruskal's Algorithm: Difference between revisions
From Rice Wiki
(Created page with "= Approach = Select edges in order of smallest to largest, using disjoint-sets to prevent cycles.") |
|||
| Line 3: | Line 3: | ||
Select edges in order of smallest to largest, using disjoint-sets to | Select edges in order of smallest to largest, using disjoint-sets to | ||
prevent cycles. | 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 | |||
Revision as of 23:59, 12 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
