Undirected, General MST

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, there are no restrictions on edge weights or graph density.

Parameters

$V$ : number of vertices
$E$ : number of edges
$U$ : maximum edge weight

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 16 of 16 algorithms


Filter Kruskal algorithm	2009	$O(E \log V)$	$O(E)$
Quick Kruskal algorithm	2006	$O(E \log V)$	$O(E)$
Pettie, Ramachandran	2002	unknown but optimal	O(E) auxiliary
Chazelle's algorithm	2000	$O(E \alpha(E, V))$	$O(E)$
Thorup (reverse-delete)	2000	$O(E \log V (\log \log V)^3)$	$O(E)$
Karger; Klein & Tarjan	1995	$O(\min(V^2, E \log V))$	$O(E)$
Kruskal’s algorithm with demand-sorting	1991	$O(E \log V)$	$O(E)$
Prim's algorithm + Fibonacci heaps; Fredman & Tarjan	1987	$O(E + V \log V)$	$O(V)$
Fredman & Tarjan	1987	O(E*beta(E, V)) where beta(m, n) = min(i such that log^(i)(n)≤m/n); this is also O(E (log-star)V)	O(E) auxiliary
Gabow et al, Section 2	1986	O(E*log(beta(E, V)))	O(E) auxiliary
Cheriton-Tarjan Algorithm	1976	$O(E \log \log V)$	$O(E)$
Yao's algorithm	1975	$O(E \log \log V)$	$O(E)$
Prim's algorithm + binary heap	1964	O(ElogV)	O(V) auxiliary
Prim's algorithm + adjacency matrix searching	1957	$O(V^2)$	$O(V)$
Kruskal's algorithm	1956	$O(E \log E)$	$O(E)$
Borůvka's algorithm	1926	$O(E \log V)$	$O(V)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms