Minimum Spanning Tree

For a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree
and connects all the vertices together. A single graph can have multiple spanning trees.
A Spanning Tree is a tree which have V vertices and V-1 edges. All nodes in a spanning tree are
reachable from each other.
A Minimum Spanning Tree(MST) or minimum weight spanning tree for a weighted,
connected, undirected graph is a spanning tree having a weight less than or equal to the weight of
every other possible spanning tree. The weight of a spanning tree is the sum of weights given to
each edge of the spanning tree. In short out of all spanning trees of a given graph, the spanning
tree having minimum weight is MST.
Necessary conditions for Minimum Spanning Tree:
1. It must not form a cycle i.e. no edge is traversed twice.
2. There must be no other spanning tree with lesser weight.

General properties of minimum spanning tree:

1. If we remove any edge from the spanning tree, then it becomes disconnected.
Therefore, we cannot remove any edge from the spanning tree.
2. If we add an edge to the spanning tree then it creates a loop. Therefore, we cannot add
any edge to the spanning tree.
3. In a graph, each edge has a distinct weight, then there exists only a single and unique

minimum spanning tree. If the edge weight is not distinct, then there can be more than
one minimum spanning tree.
4. A complete undirected graph can have an nn-2 number of spanning trees.
5. Every connected and undirected graph contains atleast one spanning tree.
6. The disconnected graph does not have any spanning tree.
7. In a complete graph, we can remove maximum (e-n+1) edges to construct a spanning
tree.
Possible Multiplicity:
If G(V, E) is a graph then every spanning tree of graph G consists of (V – 1) edges, where V is
the number of vertices in the graph and E is the number of edges in the graph. So, (E – V +
1) edges are not a part of the spanning tree. There may be several minimum spanning trees of
the same weight. If all the edge weights of a graph are the same, then every spanning tree of
that graph is minimum.
Consider a complete graph of three vertices and all the edge weights are the same then there
will be three spanning trees(which are also minimal) of the same path length are possible.
Below is the image to illustrate the same:

Each of the spanning trees has the same weight equal to 2.

Cut property:
For any cut C of the graph, if the weight of an edge E in the cut-set of C is strictly smaller than
the weights of all other edges of the cut-set of C, then this edge belongs to all the MSTs of the
graph. Below is the image to illustrate the same:
Cycle property:
For any cycle C in the graph, if the weight of an edge E of C is larger than the individual weights
of all other edges of C, then this edge cannot belong to an MST. In the above figure, in
cycle ABD, edge BD cannot be present in any minimal spanning tree because it has the largest
weight among all the edges in the cycle.
Uniqueness:
If each edge has a distinct weight then there will be only one, i.e., a unique minimum spanning
tree.

Another Example:

Applications of Minimum spanning Tree

1. Consider n stations are to be linked using a communication network & laying of
communication links between any two stations involves a cost.
The ideal solution would be to extract a subgraph termed as minimum cost spanning tree.
 2. Suppose you want to construct highways or railroads spanning several cities then we can
use the concept of minimum spanning trees.
3. Designing Local Area Networks.
4. Laying pipelines connecting offshore drilling sites, refineries and consumer markets.
5. Suppose you want to apply a set of houses with
o Electric Power
o Water
o Telephone lines
o Sewage lines
To reduce cost, you can connect houses with minimum cost spanning trees.

For Example, Problem laying

Telephone Wire.
 -----------------
--------------------------------------------------------------------------------------
Another Example
Consider the below graph:
The above graph contains 5 vertices. As we know, the vertices in the spanning tree would be the
same as the graph; therefore, V` is equal 5. The number of edges in the spanning tree would be
equal to (5 - 1), i.e., 4. The following are the possible spanning trees:
What is a minimum spanning tree?
The minimum spanning tree is a spanning tree whose sum of the edges is minimum. Consider the
below graph that contains the edge weight:
The following are the spanning trees that we can make from the above graph.
1. The first spanning tree is a tree in which we have removed the edge between the vertices
1 and 5 shown as below:
The sum of the edges of the above tree is (1 + 4 + 5 + 2): 12
2. The second spanning tree is a tree in which we have removed the edge between the
vertices 1 and 2 shown as below:
The sum of the edges of the above tree is (3 + 2 + 5 + 4) : 14
3. The third spanning tree is a tree in which we have removed the edge between the vertices
2 and 3 shown as below:
The sum of the edges of the above tree is (1 + 3 + 2 + 5) : 11
4. The fourth spanning tree is a tree in which we have removed the edge between the
vertices 3 and 4 shown as below:
The sum of the edges of the above tree is (1 + 3 + 2 + 4) : 10. The edge cost 10 is
minimum so it is a minimum spanning tree.
--------------------------------------------------------------------------------------------------------------
Methods of Minimum Spanning Tree
There are two methods to find Minimum Spanning Tree
1. Kruskal's Algorithm
2. Prim's Algorithm

Kruskal's Algorithm
An algorithm to construct a Minimum Spanning Tree for a connected weighted graph. It is a
Greedy Algorithm. The Greedy Choice is to put the smallest weight edge that does not because a
cycle in the MST constructed so far.
If the graph is not linked, then it finds a Minimum Spanning Tree.
Steps for finding MST using Kruskal's Algorithm:
1. Arrange the edge of G in order of increasing weight.
2. Starting only with the vertices of G and proceeding sequentially add each edge which
does not result in a cycle, until (n - 1) edges are used.
3. EXIT.
Example of Kruskal's Algorithm
Let's say we want to find the MST of the underlying connected, weighted, undirected graph
with 6 vertices and 9 edges-

Now as per the algorithm discussed above, to find the MST of this graph -
1. We will write all the edges sorted in ascending order according to their respective
weights
2. Then we will select the first V−1=5 edges which do not form cycles.
• Step 1 - Sort the edges in ascending order. Here is the list after sorting.
No. u v Weight
1 4 5 2
2 4 6 2
3 3 4 3
4 2 3 3
5 3 5 4
6 5 6 5
7 2 5 6
8 1 2 7
9 1 3 8
• Step 2 - Choose 5 edges from starting which do not form a cycle.
o Checking edge 4⟺54⟺5 - This is the first edge so it can't form any cycle hence
including this in result -

o Checking for edge 3⟺43⟺4 - Including this edge in the result does not form any
Cycle.

o Checking for edge 2⟺32⟺3 - Again including this edge in the result does not
form any cycle.
o Checking for edge 3⟺53⟺5 - Including this edge in the result forms a
cycle 3→4→5→33→4→5→3, hence not including this in the result.

o Checking for edge 5⟺65⟺6 - Including this edge in the result forms a
cycle 4→5→6→4, hence not including this in the result.

o Checking for edge 2⟺52⟺5 - Including this edge in the result forms a
cycle 2→3→4→5→2, hence not including this in the result.
 o Checking for edge 1⟺21⟺2 - Including this edge in the result does not form any
cycle. By including this, we have included 5 edges so now the result will
correspond to the minimum spanning tree.
After including all 55 edges, the MST will look like this –

So the weight of MST can be calculated as 7+3+3+2+2=177+3+3+2+2=17.

----------------------------------------------------------------------------------------------------
Another Example for Kruskal’s Algorithm
For Example: Find the Minimum Spanning Tree of the following graph using Kruskal's
algorithm.
Solution: First we initialize the set A to the empty set and create |v| trees, one containing each
vertex with MAKE-SET procedure. Then sort the edges in E into order by non-decreasing
weight.
There are 9 vertices and 12 edges. So MST formed (9-1) = 8 edges

Now, check for each edge (u, v) whether the endpoints u and v belong to the same tree. If they
do then the edge (u, v) cannot be supplementary. Otherwise, the two vertices belong to different
trees, and the edge (u, v) is added to A, and the vertices in two trees are merged in by union
procedure.
Step1: So, first take (h, g) edge
Step 2: then (g, f) edge.

Step 3: then (a, b) and (i, g) edges are considered, and the forest becomes

Step 4: Now, edge (h, i). Both h and i vertices are in the same set. Thus it creates a cycle. So this
edge is discarded.
Then edge (c, d), (b, c), (a, h), (d, e), (e, f) are considered, and the forest becomes.
Step 5: In (e, f) edge both endpoints e and f exist in the same tree so discarded this edge. Then
(b, h) edge, it also creates a cycle.
Step 6: After that edge (d, f) and the final spanning tree is shown as in dark lines.

Step 7: This step will be required Minimum Spanning Tree because it contains all the 9 vertices
and (9 - 1) = 8 edges
e → f, b → h, d → f [cycle will be formed]

Minimum Cost MST

Another Example of Kruskal’s Algorithm

Step 2 − Arrange all edges in their increasing order of weight

The next step is to create a set of edges and weight, and arrange them in an ascending order of
weightage (cost).

Step 3 − Add the edge which has the least weightage

Now we start adding edges to the graph beginning from the one which has the least weight.
Throughout, we shall keep checking that the spanning properties remain intact. In case, by
adding one edge, the spanning tree property does not hold then we shall consider not to include
the edge in the graph.

The least cost is 2 and edges involved are B,D and D,T. We add them. Adding them does not
violate spanning tree properties, so we continue to our next edge selection.
Next cost is 3, and associated edges are A,C and C,D. We add them again −
Next cost in the table is 4, and we observe that adding it will create a circuit in the graph. −

We ignore it. In the process we shall ignore/avoid all edges that create a circuit.

We observe that edges with cost 5 and 6 also create circuits. We ignore them and move on.

Now we are left with only one node to be added. Between the two least cost edges available 7
and 8, we shall add the edge with cost 7.
By adding edge S,A we have included all the nodes of the graph and we now have minimum cost
spanning tree.
-----------------------------------------------------------------------------------------------------------
Prim’s Method
How to Create MST Using Prim’s Algorithm
Let’s first look into the steps involved in Prim’s Algorithm to generate a minimum spanning tree:
• Step 1: Determine the arbitrary starting vertex.
• Step 2: Keep repeating steps 3 and 4 until the fringe vertices (vertices not included in
MST)remain.
• Step 3: Select an edge connecting the tree vertex and fringe vertex having the minimum
weight.
• Step 4: Add the chosen edge to MST if it doesn’t form any closed cycle.
• Step 5: Exit
Using the steps mentioned above, we are supposed to generate a minimum spanning tree
structure. Let’s have a look at an example to understand this process better.
Graph G(V, E) given below contains 9 vertices and 12 edges. We are supposed to create a
minimum spanning tree T(V’, E’) for G(V, E) such that the number of vertices in T will be 9 and
edges will be 8 (9-1).
• Primarily, to begin with the creation of MST, you will choose an arbitrary starting vertex.
Let’s say node A is your starting vertex. This means it will be included first in your tree
structure.

• After the inclusion of node A, you will look into the connected edges going outward from
node A and you will pick the one with a minimum edge weight to include it in your T(V’,
E’) structure.
• Now, you have reached node B. From node B, there are two possible edges out of which
edge BD has the least edge weight value. So, you will include it in your MST.

• From node D, you only have one edge. So, you will include it in your MST. Further, you
have node H, for which you have two incident edges. Out of those two edges, edge HI
has the least cost, so you will include it in MST structure.
• Similarly, the inclusion of nodes G and E will happen in MST.

• After that, nodes E and C will get included. Now, from node C, you have two incident
edges. Edge CA has the tiniest edge weight. But its inclusion will create a cycle in a tree
structure, which you cannot allow. Thus, we will discard edge CA as shown in the image
below.
 • And we will include edge CF in this minimum spanning tree structure.

• The summation of all the edge weights in MST T(V’, E’) is equal to 30, which is the least
possible edge weight for any possible spanning tree structure for this particular graph.

-----------------------------------------------------------------------------------------------------------------------------------
Another Example for Prim’s algorithm

Step 1 - Choose any arbitrary node as root node

In this case, we choose S node as the root node of Prim's spanning tree. This node is arbitrarily
chosen, so any node can be the root node. One may wonder why any video can be a root node.
So the answer is, in the spanning tree all the nodes of a graph are included and because it is
connected then there must be at least one edge, which will join it to the rest of the tree.
Step 2 - Check outgoing edges and select the one with less cost
After choosing the root node S, we see that S,A and S,C are two edges with weight 7 and 8,
respectively. We choose the edge S,A as it is lesser than the other.
Now, the tree S-7-A is treated as one node and we check for all edges going out from it. We
select the one which has the lowest cost and include it in the tree.

After this step, S-7-A-3-C tree is formed. Now we'll again treat it as a node and will check all the
edges again. However, we will choose only the least cost edge. In this case, C-3-D is the new
edge, which is less than other edges' cost 8, 6, 4, etc.

After adding node D to the spanning tree, we now have two edges going out of it having the
same cost, i.e. D-2-T and D-2-B. Thus, we can add either one. But the next step will again yield
edge 2 as the least cost. Hence, we are showing a spanning tree with both edges included.
We may find that the output spanning tree of the same graph using two different algorithms is
same.
---------------------------------------------------------------------------------------------------------