Alan M. Frieze showed that given a complete graph on n vertices, with edge weights that are independent identically distributed random variables with distribution function satisfying , then as n approaches +∞ the expected weight of the MST approaches , where is the Riemann zeta function.
One Tree Hill | One Tree Hill (TV series) | tree | Christmas tree | Herbert Beerbohm Tree | Porcupine Tree | The Joshua Tree | The Hanging Tree | Quebracho tree | minimum wage | Joshua Tree National Park | Under the Yum Yum Tree | Happy Tree Friends | Tree of Life | Tree of Knowledge | tree line | Tree | Oak Tree | Maunder Minimum | tree of life | Tea Tree Plaza Interchange | Rockin' Around the Christmas Tree | Radial tree | Joshua Tree | The Tree | The Learning Tree | The Juniper Tree | The Casuarina Tree | Peepal Tree Press | Our Father Who Art in The Tree |
The simplest algorithm to find an EMST in two dimensions, given n points, is to actually construct the complete graph on n vertices, which has n(n-1)/2 edges, compute each edge weight by finding the distance between each pair of points, and then run a standard minimum spanning tree algorithm (such as the version of Prim's algorithm or Kruskal's algorithm) on it.
Since there are O(n) edges, this requires O(n log n) time using any of the standard minimum spanning tree algorithms such as Borůvka's algorithm, Prim's algorithm, or Kruskal's algorithm.