Wolfram Research

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.

Details and Options

If “Graph” is specified, show the Graph.

Examples

Basic Examples

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

If “Graph” is specified, show the Graph:

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

Possible Issues

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

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

Resource History

  • Date Created: 31 January 2019
  • Latest Update: 19 April 2019

License Information