Kruskal's Algorithm

Kruskal's 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>

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{n - m} = v_1, v_2, \ldots, v_{ n - m} } , the MST of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} should be that of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{n-1}} plus the edge that connects to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_n} that is the shortest.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E ) }

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)