Kruskal's Algorithm: Difference between revisions
No edit summary |
|||
Line 1: | Line 1: | ||
{{Infobox Algorithm|runtime= | {{Infobox Algorithm|runtime=O(E log E)|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked"> | ||
== Kruskal's Algorithm == | |||
</aside><span></span> | |||
= Approach: Greedy = | = Approach: Greedy = |
Revision as of 18:06, 20 March 2024
<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">
Kruskal's Algorithm
</aside>
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)