Introduction
What is a Spanning Tree?
Given a connected, edge-weighted undirected graph $G=(V,E)$, a spanning tree of $G$ is a tree that spans $G$ and is a subgraph of $G$.
What is a Minimum Spanning Tree?
A minimum spanning tree (MST) or minimum weight spanning tree is a spanning tree with the minimum possible total edge weight.
Algorithm
There are two famous algorithms for finding the Minimum Spanning Tree.
Kruskal’s Algorithm
- Sort all the edges in an non-decreasing order according to their weight.
- Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If not, include it, else, discard it.
- Repeat step2 until there are V-1 edges in the spanning tree.