Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 KruskalAlgorithm

Source Notebook

Find the minimal spanning tree for a given set of points in Euclidean space

Contributed by: Ed Pegg Jr

ResourceFunction["KruskalAlgorithm"][pts]

finds the minimal spanning tree for pts.

ResourceFunction["KruskalAlgorithm"][pts,"Graph"]

shows the minimal spanning tree for pts as a Graph.

Examples

Basic Examples (1) 

Return a minimal spanning tree for a given set of points:

In[1]:=
points = Select[Tuples[Range[4], {2}], #[[1]] != #[[2]] &];
In[2]:=
ResourceFunction["KruskalAlgorithm"][points]
Out[2]=

Scope (1) 

If "Graph" is specified, the Graph is shown:

In[3]:=
ResourceFunction["KruskalAlgorithm"][ Select[Tuples[Range[5], {2}], #[[1]] != #[[2]] &], "Graph"]
Out[3]=

Possible Issues (1) 

The minimal spanning tree is not necessarily unique:

In[4]:=
ResourceFunction["KruskalAlgorithm"][ RandomSample[ Select[Tuples[Range[5], {2}], #[[1]] != #[[2]] &]], "Graph"]
Out[4]=

Neat Examples (2) 

Show a minimum spanning tree for a square lattice grid:

In[5]:=
ResourceFunction["KruskalAlgorithm"][ SortBy[Tuples[Range[9], {2}], Sqrt[#[[1]]/ #[[2]]] &], "Graph"]
Out[5]=

Show a minimum spanning tree for a regular grid in three dimensions:

In[6]:=
ResourceFunction["KruskalAlgorithm"][ SortBy[Tuples[Range[4], {3}], Sqrt[#[[1]]/ #[[2]]] &], "Graph"]
Out[6]=

Requirements

Wolfram Language 11.3 (March 2018) or above

Version History

  • 2.0.0 – 19 April 2019
  • 1.0.0 – 31 January 2019

License Information