Kruskal’s Algorithm in Swift

Get the smallest edge!

Kruskal’s is a minimum spanning tree algorithm. The approach is to pick the smallest edge repeatedly so long as there is not a cycle with the spanning tree created so far.

Let us see this in detail through an example, before giving that all-important Swift code (see the Gist towards the bottom of this article).

Prerequisites:

• Some experience of trees and graphs (a sprinkle of graph theory helps!)
• Closures (one is used to define the minimum edge in the code below)

Terminology

Vertex: A point where edges intersect or branch (also known as a node, plural vertices)

Edges: The connections between vertices, containing a weight

Path: A collection of edges and nodes between vertices

Graph: A collection of nodes and edges

Spanning tree: A spanning tree is a subset of a Graph, which has all the vertices covered with minimum possible number of edges

Motivation

Kruskal’s algorithm is a greedy approach for finding a minimum spanning tree. This lends it to sorting, and it is certainly something the budding Computer Science student should know something about.