Minimum Spanning Tree: Algorithms Explained with Examples

An undirected graph is one where edges have no direction. Therefore, each edge connects two vertices in both directions.  You can travel between the connected vertices in both directions. Because the edges have no direction, each connection works both ways.

In the graph above, the movement works like this:

• From A, you can go to B, D, or C
• From B, you can go to A or C
• From C, you can go to B, D, or A
• From D, you can go to A or C

A connected graph is one where there is a path between every pair of vertices. Hence, you can reach any vertex from any other vertex in the graph. Even though not all vertices are directly connected to each other, every vertex is reachable through some path.

How the movement works in the graph above:

• From A, you can go to C, and then to B or D
• From B, you can go to C and then to A or D
• From C, you can go directly to A, B, or D
• From D, you can go to C, and then to A or B

A spanning tree is one of the simplest and most important structures we can extract from a graph. A spanning tree is a subgraph of a connected and undirected graph. It includes all the vertices from the original graph but uses just enough edges to keep everything connected without forming any cycles. So, if your graph has five vertices, the spanning tree will also have five vertices but only four edges. That’s because a spanning tree always has one less edge than vertices.

The total number of spanning trees that can be formed from a complete graph with n vertices is given by the formulae = n(n-2).

If we have n = 5, the maximum number of possible spanning trees is equal to 5(5-2) = 15. Therefore, a complete graph with 5 vertices can generate 15 distinct spanning trees.

Cost and Edge Weight

Every connection between two vertices has a number tied to it. This number is called the edge weight. It could mean distance, money, time, or any value you want to minimise. When you choose a bunch of these edges to build your tree, the total of all these weights is your cost.

The minimum spanning tree picks the edges so that this cost stays as low as possible. You keep only the useful connections and skip the ones that add extra weight.

Consider the weights in the example that forms a spanning tree: 

Let’s take five vertices: A, B, C, D, and E. They are connected with weights, as shown in the diagram.

The weight of this tree = 5+7+6+9 = 27

There’s another possible tree: 

Now, let’s look at the total weight:

Total weight = 9+4+5+7 = 25

Similarly, we can generate more trees. However, only one can be the minimum spanning tree in this example. 

The MST will be the tree with the least total weight:

Total weight: 23

The Cost Table

A cost table or adjacency matrix with weights is a simple way to show how all the vertices in a graph are connected and what it "costs" to travel between them. In the case of a weighted graph, this cost represents edge weights like distance, time, or any metric the problem is optimising for.

Amongst all the possible cases of a spanning tree, a minimum spanning tree is the one for which the sum of all edge weights is minimum. Every vertex or node must be part of the structure, and the total cost of connecting everything should be as low as possible.

In real life, you can think of examples like this one: 

Let’s say you have a group of villages that need to be connected to a central gas supply. Once the main supply reaches one village, gas pipelines need to be laid out from that point to all the other villages.  There are several ways to connect these villages, and each route comes with a different cost.

Laying gas pipelines is expensive. You have to dig trenches, work through tricky terrain, and also think about how much the cost is to maintain those pipelines over time. Some paths may be longer, some may run through hills, and others might face environmental restrictions. All of these factors can be considered as the cost of an edge in a graph.

In this setup, every village becomes a vertex, and each possible pipeline route is an edge with a cost. Once you build this graph, you can find the minimum spanning tree to get the most cost-effective way to connect all the villages with the least total pipeline length.

General properties of a minimum spanning tree:

1. Removing Edge Breaks Connectivity‍

Removing even one edge from a spanning tree will no longer connect all the vertices. The graph will become disconnected, and it will no longer be a tree.

2. Adding an Edge Forms a Cycle‍

A tree is, by definition, a cyclic. So, if you try to add any extra edge to a spanning tree, it creates a loop. That loop violates the tree structure.

3. Unique Tree for Distinct Weights‍

If every edge in the graph has a unique weight, then only one unique minimum spanning tree is possible. However, if weights are repeated, multiple valid MSTs with the same total weight could exist.

4. Spanning Trees in a Complete Graph‍

A complete undirected graph with n vertices can have exactly n^(n−2) spanning trees. This result comes from Cayley’s Theorem and shows how more possible trees increase rapidly with more nodes.

5. Every Connected Graph Has a Spanning Tree‍

As long as a graph is connected and undirected, it will have at least one spanning tree. That’s because there's always a way to connect all vertices without cycles.

6. Disconnected Graphs Have None‍

If the graph is not connected, creating a spanning tree is impossible because you can’t reach all the nodes.

7. Edge Reduction in Complete Graphs‍

In a complete graph, you can remove up to (e − n + 1) edges, where e is the number of edges and n is the number of nodes. It will still be able to form a spanning tree. Beyond that, the graph becomes disconnected.

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.

For a comprehensive article on the algorithm, read: Kruskal Algorithm In C

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.

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.

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. 

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?‍

Choosing between the Prim algorithm and the Kruskal algorithm depends on the graph. Prim works best for dense graphs with many edges, while Kruskal is better for sparse graphs. Both find the minimum spanning tree. The big difference is that Kruskal can handle disconnected graphs, resulting in a minimum-spanning forest if needed.