# Introduction to Minimum Spanning Tree (MST)

**What is a Spanning Tree?**

In an undirected and connected graph G=(V,E), a spanning tree is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges. A graph may have several spanning trees. The cost of the spanning tree is the sum of the weights of all the edges in the tree

**What is a Minimum Spanning Tree?**

A **minimum spanning tree (MST)** or **minimum weight spanning tree** is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. Number of edges in MST: V-1 (V – no of vertices in Graph).

**Example**:

Algorithms for finding the Minimum Spanning Tree:

**Applications**:

Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids. Also used in

- Approximating travelling salesman problem
- Approximating multi-terminal minimum cut problem
- Approximating minimum-cost weighted perfect Cluster Analysis
- Handwriting recognition
- Image segmentation
- Circuit design

**Reference – ****wiki**