Table of Contents

Minimum Spanning Trees (MSTs) via Kruskal and Prim

Sailboat. Used on a post about MSTs.

Spanning trees streamline connections in algorithmic design. For example, a spanning tree of a graph is a tree that includes all of its vertices and a subset of its edges, forming a connected and acyclic subgraph. 

Spanning trees aid in creating optimal network structures and routing strategies, such as finding the most efficient way to establish connections between multiple networked locations, while minimizing costs and ensuring all locations remain accessible. 

A particularly helpful type of spanning tree is the minimum spanning tree (MST). MSTs are the smallest connected subgraph that spans all the vertices of a given graph, minimizing the total edge weights.

Graph vs spanning tree. Used on a post about MSTs.

Graph vs Spanning Tree (Source)

🌸👋🏻 Enjoying this post? Get the next issue of [ret]2read. Once a month, I’ll email you whatever’s on my mind, usually Apple security research, offensive security, open source software freedom, and operating system internals.

Minimum spanning trees

A MST of a connected, undirected graph is a subset of its edges that forms a tree, including all the vertices, while minimizing the total edge weight.

The goal is to establish the most efficient network of connections without creating cycles. MSTs help answer questions like, “how can we connect a set of cities with roads while (1) minimizing the construction cost and (2) ensuring each city is reachable from every other city”? 

Graph vs MST. Used on a post about MSTs.

Graph vs MST (source)

Properties 

  1. Optimality
    • MSTs ensure the most cost-effective connectivity among all vertices by selecting the minimum weight edges.
  2. Uniqueness
    • The MST is unique when all edge weights are distinct; otherwise several spanning trees may share the minimum total weight.
  3. Spanning property
    • The tree spans all vertices of the original graph, ensuring no vertex is isolated.
  4. Cycle-free structure
    • MSTs lack cycles, which avoids redundancy and ensures a “well-defined” structure.

MST Algorithms

Several algorithms can help find the MST of a graph. Two of the most well-known are Prim’s algorithm and Kruskal’s algorithm. 

Note that both Prim’s and Kruskal’s algorithms find MSTs in weighted graphs, albeit with different approaches to selecting edges. In other words, they help solve similar problems, but they use distinct strategies for determining the MST.

Prim’s algorithm

Prim’s algorithm builds an MST by adding the smallest edge at each step, starting from a random node. It is well-suited for dense graphs and scenarios where the graph is highly connected, unlike Kruskal’s algorithm. 

Visualize Prim’s spanning trees through this simulator. 

Steps

Again, Prim’s algorithm is a greedy algorithm used to find the MST of a connected, undirected graph. It does this by choosing the locally optimal solution at each step, hoping to find the global optimum. Prim’s algorithm (especially the O(V²) adjacency-matrix version) performs well on dense graphs, where the number of edges is close to the maximum possible. The algorithm’s time complexity is O(V^2) with an adjacency matrix representation of the graph. However, a binary-heap priority queue gives O(E log V); a Fibonacci heap gives O(E + V log V).

Here is how the algorithm accomplishes this: 

  1. Initialization
    1. Start with any vertex as the initial node.
    2. Create a set that will hold the vertices included in the MST.
  2. Grow the tree
    1. At each step, consider the edges that connect vertices in the MST set to those outside the set.
    2. Choose the edge with the smallest weight that connects a vertex in the MST to a vertex outside the MST.
    3. Add the selected edge and the associated vertex to the MST set.
  3. Repeat
    1. Repeat the process until all vertices are within the MST set.
  4. Result
    1. The resulting set of edges forms the MST.

Program 

prim's algorithm pseudocode
input: a connected, undirected graph g with vertices v and edges e, and weights associated with each edge.
1. initialize an empty set mst to store the edges of the minimum spanning tree.
2. select an arbitrary starting vertex s from g.
3. for each vertex v in g, set key[v] = infinity and parent[v] = nil. then set key[s] = 0.
4. initialize a priority queue q with all vertices in g, using key[v] as each vertex's priority.
5. while q is not empty:
a. extract the vertex u with the minimum key from q.
b. if parent[u] is not nil, add the edge (parent[u], u) to mst.
c. for each vertex v adjacent to u:
1. if v is in q and the weight of the edge (u, v) is less than key[v]:
a. set parent[v] = u.
b. update key[v] in q to the weight of (u, v).
6. return mst, which contains V – 1 edges.
// time complexity: O(E log V) with a binary heap, O(E + V log V) with a fibonacci heap,
// or O(V^2) with an adjacency matrix and a plain array instead of a heap.

Applications

This algorithm is commonly used in networking and circuit design. Prim’s algorithm is also employed in cluster analysis, where it helps identify relationships between data points. Now that we understand Prim’s algorithm, let’s move on to Kruskal’s algorithm.

🌸👋🏻 Enjoying this post? Get the next issue of [ret]2read. Once a month, I’ll email you whatever’s on my mind, usually Apple security research, offensive security, open source software freedom, and operating system internals.

Want your company or product in front of [ret]2read readers?
One sponsor per issue →

Kruskal’s algorithm

TLDR: Kruskal’s Algorithm iteratively adds the smallest edge that does not form a cycle until the MST contains V − 1 edges (or all edges have been processed), building the MST.

Kruskal’s algorithm finds the MST of a connected graph. It is also a greedy algorithm, prioritizing edges based on their weights by adding the smallest available edge at each step. 

On a disconnected graph, Kruskal’s algorithm naturally produces a minimum spanning forest (one MST per component). 

To do this, it employs a disjoint-set data structure. The algorithm’s time complexity is O(E log E), where E is the number of edges. This characteristic makes it particularly fast for sparse graphs.

Thus, Kruskal’s algorithm is preferred over Prim’s for sparse graphs or situations where edge weights can be easily sorted, as it processes edges in a sorted order.

Kruskal's algorithm. Used on a post about MSTs.

Source

Steps

Remember, Kruskal’s algorithm uses a connected graph with weighted edges. It builds an MST by repeatedly adding the smallest edge that doesn’t form a cycle. 

Here is how Kruskal’s algorithm accomplishes this: 

  1. Initialization
    1. Begin with each vertex in its own disjoint set, creating a forest of singleton sets.
      1. A forest is a disjoint union of trees. 
      2. A singleton set is a set that contains exactly one element. For example, {1}, {2}, {3}, etc.
    2. Arrange the edges in non-decreasing order of their weights.
  2. Building the tree
    1. Iterate through the sorted edges.
    2. For each edge, check if including it in the MST would form a cycle. If not, add the edge to the MST.
    3. To check for cycles efficiently, use a disjoint-set data structure.
  3. Repeat
    1. Continue this process until the MST contains V − 1 edges (or all edges have been processed).
  4. Result
    1. The final set of edges forms the MST.

Example  

// the overall time complexity of kruskal's algorithm is dominated by ordering the edges by weight (step 4, plus the
// extractions in step 6a) and the disjoint-set operations within the loop (step 6b).
// ordering the edges takes O(E log E) whether you sort them (e.g. mergesort) or use a min-heap, and with union by rank
// and path compression each disjoint-set operation takes amortized O(a(V)) time, where a(V) is the inverse ackermann
// function. the total is O(E log E + E * a(V)) = O(E log E), which is the same as O(E log V).
kruskal(graph g):
1. create an empty priority queue (min-heap) q.
2. create an empty set to store the disjoint sets of vertices.
3. for each vertex v in g:
a. create a disjoint set containing only v.
b. add the set to the set of disjoint sets.
4. for each edge (u, v) in g, add (u, v, weight) to the priority queue q. with a binary heap, each insertion step
takes O(log E); building the heap from all edges at once takes O(E).
5. create an empty set to store the final minimum spanning tree (mst).
6. while the mst set has fewer than V – 1 edges and q is not empty:
a. extract the edge with the minimum weight (u, v, weight) from q. with a binary heap, this extraction of
the minimum element takes O(log E).
b. if u and v are in different disjoint sets:
i. add (u, v) to the mst set.
ii. merge the disjoint sets containing u and v.
7. return the mst set. if g is disconnected, the result is a minimum spanning forest.
disjointset (with union by rank and path compression):
1. makeset(v): O(1) create a new set with a single element v.
2. findset(v): amortized O(a(V)) return the representative of the set containing v.
3. union(u, v): amortized O(a(V)) merge the sets containing u and v into a single set.

Applications

Like Prim’s algorithm, Kruskal’s algorithm is employed in network design and cluster analysis. However, it is not as common in circuit design.

If you are following my algorithm series, you may know these algorithms enable alternative investment funds to optimize cost-efficient connections between various financial nodes, enhancing data flow and decision-making processes.

🌸👋🏻 Enjoying this post? Get the next issue of [ret]2read. Once a month, I’ll email you whatever’s on my mind, usually Apple security research, offensive security, open source software freedom, and operating system internals.

Conclusion on MSTs

In short, the MST is a notable type of spanning tree that has two notable algorithms associated with it: Prim’s and Kruskal’s. 

Prim’s algorithm is best suited for finding the MST of a connected, weighted graph where the graph is dense (i.e., it has many edges). It is commonly used in network design, cluster analysis, and electronic circuit layouts. 

On the other hand, Kruskal’s algorithm is ideal for finding MSTs of connected, weighted graphs where the graphs are sparse, meaning they have fewer edges. Kruskal’s algorithm, like Prim’s, is also used in network design and clustering analysis, but it is not as common in circuit design.

Overall, I hope you enjoyed this post on MST algorithms. If you want to learn more about algorithms, I recommend reading Graph Algorithm Basics, BFS, and DFS. 

Portrait of Olivia Gallucci in garden, used in LNP article.

Written by Olivia Gallucci

Olivia is senior security engineer, certified personal trainer, and freedom software advocate. She writes about offensive security, open source software, and professional development.

Discover more from [ret]2read

A Monthly OS Internals Publication by Olivia Gallucci. Subscribe now to keep reading and get access to the full archive.

Continue reading