Introduction

A minimum spanning tree (MST) is a fundamental concept in graph theory and computer science. It refers to a subset of edges in an undirected, connected graph that connects all the vertices together while minimizing the total sum of edge weights. In simpler terms, a minimum spanning tree is a tree (a connected acyclic graph) that spans all the vertices of the original graph while using the least possible total edge weight.

Defination

A Minimum Spanning Tree (MST) is a fundamental concept in graph theory and computer science. Given an undirected graph G(V, E) with vertices V and edges E, a Minimum Spanning Tree is a subset of the edges that forms a connected subgraph while including all the vertices and minimizing the total sum of edge weights.

Formally, let’s denote the graph as G(V, E), where:

  • V is the set of vertices: {v1, v2, …, vn}.
  • E is the set of edges, where each edge is represented as a tuple (vi, vj) with associated weights: {e1 = (v1, v2, w1), e2 = (v1, v3, w2), …, em = (vk, vl, wm)}.

A Minimum Spanning Tree, denoted as MST(V, E’), is a subset of the edges E’ that satisfies the following properties:

  1. E’ ⊆ E (The edges in the MST are a subset of the original edges).
  2. The subgraph (V, E’) is connected (There exists a path between any two vertices in the MST).
  3. The subgraph (V, E’) has no cycles (It is a tree, which is acyclic by definition).
  4. The sum of the weights of the edges in E’ is minimized among all possible spanning trees of G.

Key characteristics of a minimum spanning tree:

  1. Connectedness: The minimum spanning tree must connect all the vertices of the original graph. This means that you can travel from any vertex to any other vertex in the tree by following the edges.
  2. Acyclic: A tree is by definition an acyclic graph, so the minimum spanning tree must also be acyclic. There should be no cycles in the tree.
  3. Total Edge Weight Minimization: The primary goal of finding a minimum spanning tree is to minimize the total sum of edge weights. In other words, the sum of the weights of the selected edges should be as small as possible.

Example of minimum spanning tree(MST)

Suppose you have the following graph with weighted edges:

   A---2---B
  /|       |\
1  |       |  3
  \|       |/
   C---5---D

In this graph, the nodes are represented by letters (A, B, C, D), and the numbers on the edges represent the weights of those edges.

To find the minimum spanning tree, you want to find a subset of the edges that connects all the nodes together with the minimum possible total weight. Here’s one possible MST for the above graph:

   A---2---B
  /|       
1  |       
  \|       
   C---5---D

In this MST, the selected edges are AB (weight 2), AC (weight 1), and CD (weight 5), for a total weight of 8. This tree connects all the nodes together while minimizing the total edge weight.

Please note that there can be multiple valid minimum spanning trees for a given graph if there are edges with the same weight. The example above is just one possible MST for the given graph.

Algorithms to find a minimum spanning tree

Here are some popular algorithms to find an MST:

  1. Kruskal’s Algorithm: Kruskal’s algorithm works by sorting all the edges of the graph by their weights and then gradually adding edges with the smallest weights to the MST, ensuring that no cycles are formed. Union-Find data structures are commonly used to keep track of connected components and detect cycles efficiently.
  2. Prim’s Algorithm: Prim’s algorithm starts with an arbitrary vertex and repeatedly adds the edge with the smallest weight that connects a vertex in the MST to a vertex outside the MST. This process continues until all vertices are included in the MST. It uses a priority queue (min-heap) to efficiently find the minimum-weight edge.

Application of minimum spanning tree

Minimum spanning trees have applications in various fields, including:

  • Network Design: Designing efficient and cost-effective communication networks or transportation systems.
  • Circuit Design: Designing electronic circuits with the least possible interconnection cost.
  • Cluster Analysis: Grouping data points into clusters while minimizing the distances between points in the same cluster.
  • Geographic Information Systems: Creating maps with minimal distance between landmarks.

more related content on Data Structure and Algorithms(DSA)

JOIN OUR NEWSLETTER
And get notified everytime we publish a new blog post.