Kruskal's Algorithm: Difference between revisions
From Rice Wiki
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
{{Infobox Algorithm|runtime= | {{Infobox Algorithm|runtime=O(E log E)|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}} | ||
= 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 disjoint set (aka. 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). |
Latest revision as of 18:06, 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.
Implementation
Kruskal(G): let A be an empty graph for each v in V: makeSet(v) sort E in nondecreasing order by weight for each (u,v) in E: if findSet(u) != findSet(v): A = A U {(u,v)} Union(u,v) return A
Analysis
Sort edges + E (cycle?) + (V - 1) adding edge
Disjoint set allows O(log V) cycle checking and O(log V) edge adding.
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)