Mastering Minimum Spanning Tree (MST): Detailed Guide with C Implementation

Learn Minimum Spanning Tree (MST) algorithms with step-by-step explanations, pseudo code, and C implementation in this comprehensive guide.

Mastering Minimum Spanning Tree (MST): Detailed Guide with C Implementation
Photo by Fabrice Villard / Unsplash

Introduction

A Minimum Spanning Tree (MST) is a fundamental concept in graph theory and computer science. It is a subset of the edges of a connected, undirected graph that connects all the vertices together without any cycles and with the minimum possible total edge weight. MSTs are crucial in various applications, such as network design, clustering, and many optimization problems. In this blog, we will delve into the details of MST algorithms, provide step-by-step logic explanations, present pseudo code, and guide you through implementing MST in C. By the end of this article, you will have a thorough understanding of MST and how to apply it in your programming projects.

Algorithm Details

There are two primary algorithms for finding the MST of a graph: Kruskal’s Algorithm and Prim’s Algorithm. We will cover both algorithms, explain their logic, and provide pseudo code for each.

Kruskal’s Algorithm

Kruskal’s Algorithm works by sorting all the edges in the graph by their weight and then adding edges to the MST one by one, ensuring no cycles are formed.

Step-by-Step Explanation

  1. Sort All Edges: Sort all edges in the graph by their weight.
  2. Initialize MST: Create an empty set for the MST.
  3. Add Edges: Add edges to the MST from the sorted list, ensuring that no cycles are formed. Use the Union-Find data structure to check for cycles.
  4. Repeat: Repeat the process until the MST contains V−1V-1V−1 edges, where VVV is the number of vertices in the graph.

Pseudo Code

function Kruskal(Graph):
    MST ← ∅
    for each edge in Graph, sorted by weight:
        if adding the edge to MST does not form a cycle:
            add the edge to MST
    return MST

Prim’s Algorithm

Prim’s Algorithm starts with a single vertex and grows the MST by adding the cheapest edge from the tree to a vertex outside the tree.

Step-by-Step Explanation

  1. Initialize: Start with a single vertex, add it to the MST.
  2. Select Edge: Select the smallest edge connecting a vertex in the MST to a vertex outside the MST.
  3. Add Edge: Add the selected edge and the new vertex to the MST.
  4. Repeat: Repeat the process until all vertices are included in the MST.

Pseudo Code

function Prim(Graph, start):
    MST ← ∅
    visited ← {start}
    while MST does not contain all vertices:
        edge ← smallest edge from visited vertices to unvisited vertices
        add edge to MST
        add the connected vertex to visited
    return MST

Implementation in C

Here, we will implement Kruskal’s Algorithm in C.

Code

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct {
    int u, v, w;
} Edge;

Edge edges[MAX];
int parent[MAX];
int n, e;

int find(int i) {
    while (parent[i] != i)
        i = parent[i];
    return i;
}

void union1(int i, int j) {
    int a = find(i);
    int b = find(j);
    parent[a] = b;
}

void kruskal() {
    int i, j, u, v;
    Edge temp;
    int mincost = 0;

    for (i = 0; i < e; i++) {
        for (j = i + 1; j < e; j++) {
            if (edges[i].w > edges[j].w) {
                temp = edges[i];
                edges[i] = edges[j];
                edges[j] = temp;
            }
        }
    }

    for (i = 0; i < n; i++)
        parent[i] = i;

    printf("Edges in MST:\n");
    for (i = 0; i < e; i++) {
        u = edges[i].u;
        v = edges[i].v;

        int uRep = find(u);
        int vRep = find(v);

        if (uRep != vRep) {
            printf("Edge (%d, %d) with weight %d\n", u, v, edges[i].w);
            mincost += edges[i].w;
            union1(u, v);
        }
    }

    printf("Minimum cost of the spanning tree: %d\n", mincost);
}

int main() {
    int i;
    printf("Enter the number of vertices and edges:\n");
    scanf("%d %d", &n, &e);

    printf("Enter the edges (u v w):\n");
    for (i = 0; i < e; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }

    kruskal();

    return 0;
}

Explanation of C Code

  1. Graph Representation: The graph edges are stored in an array edges of structures containing u, v, and w (representing the two vertices and the weight of the edge).
  2. Union-Find Structure: The parent array is used to implement the Union-Find data structure, which helps in detecting cycles.
  3. Kruskal’s Algorithm Function: The kruskal function sorts the edges by weight, then iteratively adds edges to the MST while ensuring no cycles are formed.
  4. Main Function: The main function takes input for the number of vertices and edges, reads the edges, and then calls the kruskal function to compute and print the MST.

Time and Space Complexity

Time Complexity

  • Kruskal’s Algorithm: The time complexity is O(ElogE+ElogV), where E is the number of edges and V is the number of vertices. Sorting the edges takes O(Elog⁡E) and the Union-Find operations take O(log⁡V) each.
  • Prim’s Algorithm: Using a priority queue, the time complexity is O(ElogV).

Space Complexity

Both Kruskal’s and Prim’s algorithms have a space complexity of O(V+E), accounting for storing the graph and the auxiliary data structures.

Usage

Minimum Spanning Trees are used in various practical applications:

  • Network Design: Designing least-cost networks, such as telecommunications and computer networks.
  • Clustering: In machine learning, MSTs can help in clustering data points.
  • Approximation Algorithms: MSTs are used in approximating solutions to NP-hard problems like the Traveling Salesman Problem (TSP).

Conclusion

Minimum Spanning Trees are essential in both theoretical and practical aspects of computer science. By understanding and implementing Kruskal’s and Prim’s algorithms, you can solve various optimization problems efficiently. We hope this guide has provided you with a comprehensive understanding of MST and its applications.

If you found this blog helpful or have any suggestions for improving it, please leave your feedback or suggestions in the comments. Your input is valuable in helping me create better and more informative content for you!

Subscribe to rahulv.dev | blog

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe