Minimum Spanning Tree: Algorithms Explained with Examples

Minimum spanning tree algorithms are crucial for efficiently connecting all vertices in a graph with the least total edge weight. There are several algorithms to solve the MST problem and each have its unique approach and strengths. 

Borůvka’s Algorithm

Borůvka’s algorithm was the first to find the minimum spanning tree and was introduced in 1926. It gradually merging components of the graph using the smallest edge between them.

How it works

• Start by treating each vertex as its own component.
• Find the smallest edge from each component to another component.
• Add the smallest edge to the MST and merge the two components.
• Repeat until all components are connected.

Jarník’s (“Prim’s”) Algorithm

Prim’s algorithm is also known as Jarník’s algorithm. It grows the MST one vertex at a time. It ensures that the tree remains connected while choosing the smallest possible edge at each step.

How it works

• Start with any vertex and mark it as part of the MST.
• At each step, add the smallest edge that connects a vertex in the MST to one outside it.
• Repeat this until all vertices are included in the MST.‍

Improving Jarník’s Algorithm - Fibonacci heap

Improving Prim’s algorithm using a Fibonacci Heap helps reduce the algorithm’s time complexity by optimising the priority queue management, especially for dense graphs.

How it works

• Use a Fibonacci Heap to manage the priority queue of edges efficiently.
• The Fibonacci Heap allows quicker decrease-key operations, making the algorithm faster.
• This reduces the time complexity to O(E + V log V), which is especially useful for graphs with many edges.

Kruskal’s Algorithm

Kruskal’s algorithm is based on sorting all the edges by weight and adding them individually, ensuring no cycles form. It’s particularly efficient for sparse graphs.

How it works

• Sort all edges in increasing order of their weight.
• Use a Union-Find structure to check if adding an edge forms a cycle.
• If adding the edge doesn’t form a cycle, include it in the MST.
• Repeat until all vertices are connected.

‍Kruskal Algorithm for Minimum Spanning Tree

Among the different methods to find a minimum spanning tree, Kruskal’s algorithm is among the most popular. It’s known for being clean, greedy, and highly effective, especially when the graph has many edges. It stands out because it doesn’t build the tree from one vertex. Instead, it focuses on picking the cheapest possible edges while avoiding cycles.

Example of Kruskal Algorithm

Here’s how Kruskal’s algorithm builds a minimum spanning tree:

1. List all the edges in the graph, along with their weights.

2. Sort the edges in ascending order of weight, ie, from smallest to largest.

3. Start picking edges from the top of the sorted list. For each edge:

• Check if adding it to your tree would form a cycle.
• If no cycle is formed, include it in the spanning tree.
• If it creates a cycle, skip it and move to the next edge.

Repeat this process until you’ve added exactly V - 1 edges, where V is the number of vertices in the graph. Now, let’s look at how this works in the original tree:

Step 1: Start with the smallest edge

Edge chosen: DA (weight 4)

Step 2: Next smallest edge

Edge chosen: AB (weight 5)

Step 3: Next edge

Edge chosen: CD (weight 6)

Check: D is already in the tree; C is not; hence, it can be added

Step 4: Next edge

Edge chosen: BC (weight 7)

Check: B and C are already connected, and it forms a cycle, so Skip.

Step 5: Next edge

Edge chosen: CE (weight 8)

Check: C is in the tree, E is not. Hence, it can be added.

Now we have 5 vertices connected and 4 edges, so the minimum spanning tree is complete.

Key Takeaways So Far:

• Kruskal sorts edges and adds them without forming cycles.
• Union-Find efficiently detects and prevents cycle formation.
• Example graph yields MST with total weight of 23.

Prim's algorithm is your go-to method for building a minimum spanning tree by starting from one vertex and growing the tree step by step. Unlike Kruskal’s, which looks at all the edges, Prim’s keeps its focus on vertices and expands the tree by always choosing the cheapest edge that connects to an unvisited vertex. It’s like spreading out from a starting point and always picking the next closest node to attach. Because of this property, the prim algorithm doesn’t need Union-Find because it never connects two already visited vertices. It just keeps growing the tree into new vertices.

How Prim’s Algorithm Works

1. Start from any vertex (say, A).

2. Keep track of the vertices already included in the MST.

3. Pick the one with the smallest weight from all edges that connect the MST to an unvisited vertex.

4. Add that edge and the vertex to the MST.

5. Repeat steps 3 and 4 until all vertices are part of the tree.

Now, using the same graph as earlier, let’s look at how the algorithm works. We'll start Prim’s algorithm from vertex A and see how the MST is built step by step.

Initial MST Set: {A}

Available Edges from A:

AB (5)

DA (4)

Pick DA (4) since it’s the smallest.

MST Set: {A, D}

Total Weight: 4

Step 2:

Edges from MST ({A, D}):

AB (5) 

CD (6) 

ED (9) 

Pick AB (5)

MST Set: {A, D, B}

Total Weight: 4 + 5 = 9

Step 3:

Edges from MST ({A, D, B}):

CD (6)

ED (9)

BC (7)

Pick CD (6)

MST Set: {A, D, B, C}

Total Weight: 9 + 6 = 15

Step 4:

Remaining unvisited vertex: E

Edges from MST to E:

CE (8)

ED (9)

Pick CE (8)

MST Set: {A, D, B, C, E}

Total Weight: 15 + 8 = 23

The final structure of the MST, by eliminating the edges that were not taken, would look like: 

Now, let’s look at the code for the minimum spanning tree example using Prim’s algorithm:

Code

#include <stdio.h>
#include <limits.h>

#define V 5  // Number of vertices in the graph

int minKey(int key[], int mstSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (mstSet[v] == 0 && key[v] < min)
            min = key[v], min_index = v;

    return min_index;
}

void printMST(int parent[], int graph[V][V]) {
    int totalCost = 0;
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++) {
        printf("%c - %c \t%d \n", 'A' + parent[i], 'A' + i, graph[i][parent[i]]);
        totalCost += graph[i][parent[i]];
    }
    printf("Total Cost of MST: %d\n", totalCost);
}

void primMST(int graph[V][V]) {
    int parent[V];  // To store the constructed MST
    int key[V];     // Key values used to pick minimum weight edge
    int mstSet[V];  // To represent set of vertices included in MST

    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = 0;

    key[0] = 0;     // Start from vertex 0 (A)
    parent[0] = -1; // First node is always root of MST

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);

        mstSet[u] = 1;

        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }

    printMST(parent, graph);
}

int main() {
    int graph[V][V] = {
        // A  B  C  D  E
        { 0, 5, 0, 4, 0 }, // A
        { 5, 0, 7, 0, 0 }, // B
        { 0, 7, 0, 6, 8 }, // C
        { 4, 0, 6, 0, 9 }, // D
        { 0, 0, 8, 9, 0 }  // E
    };

    primMST(graph);

    return 0;
}

Output

Edge 	Weight
A - B 	5 
D - C 	6 
A - D 	4 
C - E 	8 
Total Cost of MST: 23


=== Code Execution Successful ===

How The Code Works

Step 1: The Initialisation

• key[] array is initialised with INT_MAX for all vertices.
• mstSet[] is initialised with 0 (false) for all vertices. This tracks if a vertex is included in the MST.
• parent[] stores the MST structure. Each index will hold the parent of that vertex in the tree.
• The algorithm starts from vertex 0 (which is vertex A in our example).
• Set key[0] = 0 so it's picked first, and parent[0] = -1 since it's the root.

Step 2: Loop Through Vertices

• For V-1 iterations (since an MST has V-1 edges), do the following:
  

• Find the Minimum Key Vertex Not in MST
  
  • Use minKey() to find the vertex with the smallest key[] value that’s not in mstSet[].
  • This gives us the next best vertex to add.
• Mark the Picked Vertex as Part of the MST
  
  • Set mstSet[u] = 1 to include the vertex in MST.
• Update Adjacent Vertices
  
  • Loop through all vertices v.
  • If there's an edge from u to v, and v is not in MST yet, and the edge weight is less than the current key[v], update:
    
    • key[v] = graph[u][v]
    • parent[v] = u

Step 3: Print the MST

• After the loop, parent[] holds the structure of the MST.
• Use printMST() to show the edges and calculate the total cost of the MST.

Complexity

Time Complexity: O(V²): For each vertex, we linearly scan the key[] array to find the minimum. We also check all adjacent vertices in a nested loop.

Space Complexity: O(V²) — Due to the use of an adjacency matrix of size V x V to store the graph.

Bottom Line: Kruskal sorts edges globally; Prim grows locally—both efficiently compute the minimum spanning tree.

The minimum spanning tree problem has been the primary source of numerous variants and exceptional cases, each with different constraints or objectives. These changes help to elevate the classic MST framework to run two-sided scenarios of network design, optimization, and theoretical research.

Fractional Variant and Minimum Fractional Spanning Set

The fractional variant of MST allows partial usage of edges rather than integral usage. A minimum fractional spanning set maps every edge to a nonnegative number such that for any non-trivial subset of vertices, the sum of fractions crossing the cut is at least one. The objective is to minimize the total weighted sum of these fractions. This problem can be solved within polynomial time using the ellipsoid method.

MST on Complete Graphs with Random Weights

In the case of random weights for complete graphs on which MST is considered, the weights are assigned randomly (usually uniformly). This scenario is vital in the probabilistic analysis and it also helps the researchers in understanding the expected behavior of MSTs in random networks.

k-Minimum Spanning Tree

The goal of the k-minimum spanning tree (k-MST) problem is finding a minimum total weight tree that spans exactly k vertices of the given graph, instead of all vertices. Such a variant finds its utility in situations where only a subset of nodes needs to be connected in an efficient manner.

Degree-Constrained Minimum Spanning Tree

A degree-constrained minimum spanning tree is a concept where each vertex in the resulting tree can have at most a certain number of edges (degree) incident to it. This is applicable to the network designs where physical or logical constraints limit the number of direct connections a node can have.

Distributed Minimum Spanning Tree

In a distributed environment, the distributed minimum spanning tree problem represents a scenario where a node is only aware of the edges connected to it. The emphasis is on the nodes figuring out how to assemble the MST collaboratively through local communication and computation.

Decision Trees for MST

Decision trees can be a valuable tool for illustrating the process of obtaining an MST through a comparison of edge weights. This means of an MST algorithm is used primarily in theoretical computer science to determine complexity and optimality as well as to provide proofs.

Cycle and Cut Properties in Variants

Most MST variations acknowledge a direct or indirect reference to the basic cycle (the maximum-weight edge of any cycle cannot be a part of MST) and the cut property (the minimum-cost edge crossing any cut is the one that is always in the MST) of the foundational concepts. These features aid in the drawing of algorithm and proof designs suitable for not only the MST issues but also their specialized variants.

Minimum-Cost Edge and Contraction

The least-cost edge in a graph that is uniquely minimum is the one that is included in every MST. Contraction—the method of combining connected components into individual nodes—continues to be essential in advanced MST algorithms and their variants. It facilitates the reduction of problem size and ​‍​‌‍​‍‌​‍​‌‍​‍‌complexity.

Grasping​‍​‌‍​‍‌​‍​‌‍​‍‌ minimum spanning trees concepts is not limited to algorithms only—it is primarily about recognizing and resolving real-life problems related to edge-weighted graphs, as well as utilizing those concepts properly. If you are going to be interviewed or if you just want to be more proficient in your work, then you have to be very active in solving everyday problems and practice questions.

Typical Problem Types

Basic Construction: One of the most common challenges that you will come across is given a weighted, undirected graph, how to identify such a tree, as well as, determine the sum of the weights of the minimum spanning tree. Also, keep in mind that a spanning tree of a graph with n nodes is always made up of n − 1 edges.

Road Reparation: In the case of “road reparation” style problems, you are tasked with determining the most cost-effective way to connect the cities (vertices) with road repairs while maintaining network connectivity. The main requirement in these problems is to pick those edges which will result in the lowest total cost of the network, whereas the graph will still be a spanning tree.

Topological Observability Analysis: There are also some high-level problems, for instance in the area of network design or power systems, where you may be required to examine the network's observability through the use of MST methods. The solution to these problems depends heavily on understanding how spanning trees are connected to the system's architecture.

Edge Inclusion/Exclusion: Some questions may revolve around the issue of a particular edge being in an MST - always, sometimes, or never, depending on the edge weights and the graph's structure.

Variants and Extensions: Practice problems might include finding a minimum spanning forest in disconnected graphs or working with graphs that have constraints on edge ​‍​‌‍​‍‌​‍​‌‍​‍‌selection.

Practice Problem Example

Consider the following undirected, edge-weighted graph:

• Vertices: A, B, C, D
• Edges:
  AB (weight 2), AC (weight 3), BC (weight 1), BD (weight 4), CD (weight 5)

Task:
Find the minimum spanning tree, list the edges included, and calculate the total cost.

Solution:

• Select edges in order of increasing weight: BC (1), AB (2), AC (3), BD (4), CD (5)
• Add BC (1), AB (2), and AC (3)
• Adding BD or CD would form a cycle, so stop after n − 1 = 3 edges.
• MST edges: BC, AB, AC.
• Total cost: 1 + 2 + 3 = 6

Practice and Interview Problems

Here are some classic practice and interview problems to build your skills:

• Find the minimum cost to connect all cities (road reparation).
• Determine if a given edge is part of all possible MSTs.
• Calculate the number of distinct spanning trees in a given undirected graph.
• Apply MST algorithms to solve topological observability analysis in networks.
• Given a weighted graph, find the second-best minimum spanning tree.

Regularly practicing these types of questions will help you develop a deeper understanding of spanning trees, edge selection strategies, and efficient approaches for real-world and technical interview scenarios.

Quick Note: Practice MST through construction, edge checks, and optimization in real-world network scenarios.

Both the algorithms differ in the approaches to finding the minimum spanning tree. Here are some of the important differences:

MST finds applications in various fields for optimising resources and reducing costs. These include: 

1. Network Design: The algorithm is used in planning efficient layouts for gas pipelines, electrical grids, water supply, and telecommunication lines. It is good at planning these networks at minimal cost.

2. Computer Networks: Helps build minimal wiring for LAN and WAN setups while keeping all nodes connected.

3. Road and Railway Design: The algorithm optimises road or track construction between cities with the least total distance or construction cost.

4. Cluster Analysis: MSTs are used in data mining and machine learning to group similar data points efficiently.

5. Broadcasting in Wireless Networks: with the MST algorithm all the receivers get a signal with minimal transmission power and coverage overlap.

What We’ve Learned So Far:

• Variants extend MST to subsets and constrained networks.
• Practice includes road repair and second-best MST problems.
• Real-world use optimizes infrastructure, telecom, and clustering.

As you can see, there can be a huge number of applications for the minimum spanning concepts across all domains for optimising and finding solutions. They find applications in a wide range of fields, including planning cable networks, transportation routes, image segmentation, clustering in machine learning, and even social network analysis. Therefore, learning these topics builds your foundation in problem-solving and optimisation. To learn more and build a strong tech career with real-world skills, the CCBP 4.0 Academy Program is the perfect place to start. Enroll today and get a leg up in your career. 

Why It Matters?

Minimum Spanning Trees save billions by eliminating redundant connections in real-world networks—whether laying fiber optic cables, designing power grids, or optimizing cloud infrastructure. In a hyper-connected world, even small efficiency gains scale massively, reducing costs, energy use, and deployment time while enabling robust, fault-tolerant systems essential for modern tech, logistics, and data-driven decision making.

Practical Advice for Learners

• Implement Prim/Kruskal in your language (start with sample graph).
• Solve 5 LeetCode MST problems weekly.
• Apply to a project: Optimize a map's routes using graph libraries.
• Visualize MSTs with NetworkX/Graphviz to see cycle elimination.
• Benchmark naive vs. heap-optimized Prim on large random graphs.

1. What is Kruskal algorithm?‍

The Kruskal algorithm is an algorithm for minimum spanning tree construction. It works by sorting all edges by weight and adding them one by one while avoiding going in cycles in the graph. It’s especially useful in disconnected graphs and forming a minimum spanning forest if needed.

2. Can the Prim algorithm be used for disconnected graphs?‍

No, the Prim algorithm only works on connected graphs. It builds a minimum spanning tree by growing it from a single vertex. In disconnected graphs, you would need multiple trees. The Kruskal algorithm is more suitable for forming a minimum spanning forest.

3. What’s the difference between a minimum spanning tree and a minimum spanning forest?

A minimum spanning tree connects all the vertices in a connected graph using the smallest total edge weight possible. But if the graph is disconnected, i.e., it has separate parts, you can’t connect everything with just one tree. So, a minimum spanning forest has to be used. The minimum spanning forest is basically a group of minimum spanning trees, where there is one tree for each disconnected part of the graph.

4. Algorithm for minimum spanning tree for real-world applications?‍

An algorithm for minimum spanning tree, like Prim or Kruskal, helps design efficient networks like internet cabling to road maps. These minimum spanning techniques reduce cost and complexity. In disconnected systems, a minimum spanning forest might be generated instead of a single tree.

5. Prim algorithm vs Kruskal algorithm: which is better?‍

Deciding​‍​‌‍​‍‌​‍​‌‍​‍‌ whether to use the Prim algorithm or the Kruskal algorithm is a matter of the graph. Prim is a good choice for dense graphs that have a lot of edges, whereas Kruskal works better for sparse graphs. Both algorithms produce the minimum spanning tree. The major difference is that Kruskal is capable of processing disconnected graphs, thus generating a minimum-spanning forest in such a ​‍​‌‍​‍‌​‍​‌‍​‍‌case.