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 (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 (source)
Properties
- Optimality
- MSTs ensure the most cost-effective connectivity among all vertices by selecting the minimum weight edges.
- Uniqueness
- The MST is unique when all edge weights are distinct; otherwise several spanning trees may share the minimum total weight.
- Spanning property
- The tree spans all vertices of the original graph, ensuring no vertex is isolated.
- 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:
- Initialization
- Start with any vertex as the initial node.
- Create a set that will hold the vertices included in the MST.
- Grow the tree
- At each step, consider the edges that connect vertices in the MST set to those outside the set.
- Choose the edge with the smallest weight that connects a vertex in the MST to a vertex outside the MST.
- Add the selected edge and the associated vertex to the MST set.
- Repeat
- Repeat the process until all vertices are within the MST set.
- Result
- The resulting set of edges forms the MST.
Program
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.

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


You must be logged in to post a comment.