In this chapter we shall learn about below topics:
1.1 Introduction to spanning tree
1.2 What is minimum spanning tree?
1.3 Usage of minimum spanning tree.
First thing to understand is that this topic will come under Graphs not trees.
Before solving questions related to Minimum Spanning Tree [MST], we shall take a look on what are MST?
In Minimum Spanning Tree, there is a sub part Spanning Tree.
1.1 Spanning Tree Introduction:
Given a connected undirected graph, a spanning tree of that graph is a sub graph that has all the vertices and also a tree.
Means, a spanning tree should be connected [connected to all the vertices], acyclic [should not have any cycle] and should have all the vertices.
Below is a simple graph
Below are the different number of spanning tree for that graph.
Note:
If there are “n” vertices, then a spanning tree should have “n-1” edges. In the above image, we have 4 vertices, hence our spanning tree has “4 -1 = 3” edges.
1.2 Then what is Minimum Spanning Tree?
Consider the below weighted graph:
Now you are a sales person, and let us consider each vertices as cities, and you need to visit all the places with minimum amount possible.
Below image is the solution for it.
1.3 So where do we use MST?
We use MST in
1. Network Design
2. Maps
3. Face Verification
In the next MST problems, we shall look at more complex problems with cycle and how to solve them using Prims and Kruskal’s algorithm.