What Are Minimum Spanning Trees?

Spanning trees

Given an undirected and connected graph G = (V, E), a spanning tree of the graph G is a tree that spans G (it includes every vertex of G) and is a sub-graph of G (every edge in the tree belongs to G)

Minimum spanning trees

The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. A minimum spanning tree is a spanning tree where the cost is minimum among all the spanning trees. There can also be many minimum spanning trees. A minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the traveling salesman problem, multi-terminal minimum cut problem, and the minimum cost weighted perfect matching problem. Other practical applications are:

1. Cluster Analysis
2. Handwriting recognition
3. Image segmentation

There are two famous algorithms for finding the minimum spanning tree:

• Kruskal’s Algorithm
• Prim’s Algorithm

Let’s look at an example.