Kruskal's Algorithm: Difference between revisions
From Rice Wiki
| (5 intermediate revisions 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 | 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. | ||
| Line 9: | Line 8: | ||
OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E ) | OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E ) | ||
</math> | </math> | ||
= Implementation = | |||
<pre> | |||
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 | |||
</pre> | |||
= Analysis = | = Analysis = | ||
Sort edges + E (cycle?) + (V - 1) adding edge | 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 | Sorting takes E log E | ||
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)
