Minimum Spanning Tree Example with Solution

Minimum Spanning Tree is an important part of Graph Data Structure. Basic Concepts of Minimum Spanning Tree with Example and Solution are explained here in this tutorial.

Minimum Spanning Tree is also an important topic for GATE(CS/IT) and UGC NET exam. GATE aspirants are advised to prepare minimum spanning tree tutorial very well.

Frequently Asked Questions

Questions from the following sub topics are generally asked from Minimum Spanning Tree.

What is Spanning Tree ?
What is minimum spanning tree ?
Properties of spanning tree.
Method to find the minimum spanning Tree.
Minimum Spanning Tree example with solution.

Minimum spanning tree algorithms will be explained by us in the next tutorial.

Let’s start with Spanning Tree.

What is Spanning Tree ?

A Spanning Tree is a Subset of Graph which have all the vertices of Graph and have minimum number of Edges.

We can understand the concept of Spanning Tree with an example. Let’s consider a weighted graph as shown below.

If the graph has V no. of vertices and E no. of edges, then the graph can be represented as G(V, E).
Now the spanning tree of the graph will be a tree that connect all the vertices of graph with minimum number of edges.
A graph can contain more than one Spanning Trees.

So when we’ll draw a spanning tree of the above graph, we’ll get the same no. of vertices. But . No. of edges would be 4.

The resultant spanning trees would be-

What is Minimum Spanning Tree ?

Minimum Spanning Tree is a Spanning Tree having minimum cost among all the Spanning Trees.
Cost of Spanning Tree is the sum of weight of all edges in the Tree.

For example as discussed in previous section Spanning tree having the weight equal to 10 is the minimum Spanning Tree.

Properties of Spanning Tree

There are three main properties of spanning tree.

The tree should never have a cycle.
The tree should not be disconnected.
Tree should cover all the vertices of the Graph.

If each edge a unique weight then there will be only one and unique MST.

A complete undirected graph can have number of spanning trees.
Every connected and directed graph must have at least one spanning tree.
Disconnected graph doesn’t have any spanning tree.
From a complete graph, we can construct a spanning tree by removing maximum e-n+1 no. of edges.

Methods for finding a Minimum Spanning Tree

The first method is to find out all the spanning trees possible from the graph and then finding the minimum cost spanning tree among those spanning trees.

Problem based on finding the minimum spanning tree in the given graph is always asked in GATE(CS/IT) exam.

Let’s consider the graph below. It has three vertices. Hence this graph can have spanning trees.

Here, the tree with minimum spanning cost is the 2^nd spanning tree with cost 3. This spanning tree will be the minimum spanning tree.

The problem with this method is we have to find out each spanning tree one by one and calculate the spanning cost of each tree to finally find out the MST. It will take so much time. So, to find out MST with minimum amount of time, some greedy methods are used.

Those methods are-

Prim’s Algorithm.
Kruskal’s Algorithm.

Prim’s Algorithm and Kruskal’s Algorithm are used to find minimum spanning tree in a weighted graph.

Prim’s algorithm has been explained in the next tutorial with example .

Applications of Minimum Spanning Tree

Various applications of minimum spanning Tree are as follow –

Minimum Spanning Tree is used in electrical network to reduce the wire cost that connect houses for electricity supply in home.
Concept of Minimum Spanning Tree is used telecommunication networks.
Minimum Spanning Tree is used in Google Map Application to find shortest path.
Minimum Spanning Tree is also used in designing local area networks.