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:

• Kruskal’s Algorithm
• Prim’s Algorithm

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

Also Read:

- Dijkstra Algorithm Implementation – TreeSet and Pair Class Hard
- Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Min Heap – Java Implementation Hard
- Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Priority Queue without decrease key in O(ElogV) Hard
- Graph Implementation – Adjacency List - Better| Set 2 Beginner
- Max Flow Problem – Introduction Hard
- Count number of subgraphs in a given graph Beginner
- Check if given an edge is a bridge in the graph Medium
- Maximum number edges to make Acyclic Undirected/Directed Graph Beginner