Kruskal's Algorithm: Difference between revisions
From Rice Wiki
| Line 2: | Line 2: | ||
= Approach: Greedy = | = Approach: Greedy = | ||
The approach is to try to add the smallest edges as long as they do not create a cycle. Unlike [[Prims Algorithm|Prim's algorithm]], which prevents cycles by only choosing edges that crosses a cut of nodes already in the tree and nodes that aren't, Kruskal prevents cycles using a data structure known as union-find. | The approach is to try to add the smallest edges as long as they do not create a cycle. Unlike [[Prims Algorithm|Prim's algorithm]], which prevents cycles by only choosing edges that crosses a cut of nodes already in the tree and nodes that aren't, Kruskal prevents cycles using a data structure known as disjoint set (aka. union-find). | ||
Given the MST of <math>V_{n - m} = v_1, v_2, \ldots, v_{ n - m} </math>, the MST of <math>V</math> should be that of <math>V_{n-1}</math> plus the edge that connects to <math>v_n</math> that is the shortest. | Given the MST of <math>V_{n - m} = v_1, v_2, \ldots, v_{ n - m} </math>, the MST of <math>V</math> should be that of <math>V_{n-1}</math> plus the edge that connects to <math>v_n</math> that is the shortest. | ||
Revision as of 18:00, 20 March 2024
Approach: Greedy
The approach is to try to add the smallest edges as long as they do not create a cycle. Unlike Prim's algorithm, which prevents cycles by only choosing edges that crosses a cut of nodes already in the tree and nodes that aren't, Kruskal prevents cycles using a data structure known as disjoint set (aka. union-find).
Given the MST of , the MST of should be that of plus the edge that connects to that is the shortest.
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)
