Wolfram Research

Wolfram Function Repository (Under Development)

Instant-use add-on functions for the Wolfram Language

 KruskalAlgorithm

Contributed by: Ed Pegg Jr

Source Notebook

Find the minimal spanning tree for a given set of edges

ResourceFunction["KruskalAlgorithm"][edges]

finds the minimal spanning tree for a graph given by edges.

ResourceFunction["KruskalAlgorithm"][edges,"Graph"]

finds the minimal spanning tree and shows 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

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

Resource History

  • Date Created: 31 January 2019