Minimum Spanning Tree

What is a Spanning Tree?

Given an undirected and connected graph , a spanning tree of the graph  is a tree that spans  (that is, it includes every vertex of ) and is a subgraph of  (every edge in the tree belongs to )

What is a Minimum Spanning Tree?

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. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. 

There are two famous algorithms for finding the Minimum Spanning Tree:

1. Kruskal’s Algorithm
2. Prim’s Algorithm

Kruskal’s Algorithm

Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a tree of that graph which includes every vertex and the total weight of all the edges in the tree is less than or equal to every possible spanning tree.

Algorithm

1. Arrange all the edges of the given graph G(V,E) in ascending order as per their edge weight.
2. Choose the smallest weighted edge from the graph and check if it forms a cycle with the spanning tree formed so far.
3. If there is no cycle, include this edge to the spanning tree else discard it.
4.  Repeat Step 2 and Step 3 until (V−1) number of edges are left in the spanning tree.

1. Problem

Suppose we want to find minimum spanning tree for the following graph G using Kruskal’s algorithm.

2. Problem

Suppose we want to find minimum spanning tree for the following graph G using Kruskal’s algorithm.

From the above graph we construct the following table 

Edge No.	Vertex Pair	Edge Weight
E1	(a, b)	20
E2	(a, c)	9
E3	(a, d)	13
E4	(b, c)	1
E5	(b, e)	4
E6	(b, f)	5
E7	(c, d)	2
E8	(d, e)	3
E9	(d, f)	14

Now we will rearrange the table in ascending order with respect to Edge weight 

Edge No.	Vertex Pair	Edge Weight
E4	(b, c)	1
E7	(c, d)	2
E8	(d, e)	3
E5	(b, e)	4
E6	(b, f)	5
E2	(a, c)	9
E3	(a, d)	13
E9	(d, f)	14
E1	(a, b)	20

Since we got all the 5 edges in the last figure, we stop the algorithm and this is the minimal spanning tree and its total weight is (1+2+3+5+9)=20.

Prim's Algorithm

Prim, is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a tree of that graph which includes every vertex and the total weight of all the edges in the tree is less than or equal to every possible spanning tree. 

Algorithm

1. Initialize the minimal spanning tree with a single vertex, randomly chosen from the graph.
2. Repeat steps 3 and 4 until all the vertices are included in the tree.
3. Select an edge that connects the tree with a vertex not yet in the tree, so that the weight of the edge is minimal and inclusion of the edge does not form a cycle.
4. Add the selected edge and the vertex that it connects to the tree.

1. Problem

Suppose we want to find minimum spanning tree for the following graph G using Prim’s algorithm.

2. Problem

Suppose we want to find minimum spanning tree for the following graph G using Prim’s algorithm.

Solution

Here we start with the vertex ‘a’ and proceed.

This is the minimal spanning tree and its total weight is (1+2+3+5+9)=20