Data Structure(Spanning Tree and Minimam spanning tree)

 

Spanning Tree :

👉 A spanning tree is defined as a subset of a connected undirected graph that has all the vertices covered with the minimum number of edges possible. 

👉 The spanning tree covers all the vertex present in the graph. 

👉 The only difference between a spanning tree and a graph is that a spanning tree does not have a cycle and a minimum number of edges possible.

👉 The spanning tree must have an equal number of vertices as of the given graph. 

👉 In the spanning tree, the total number of edges is n-1. Here, n is the number of vertices in the graph. The edges of the spanning tree may or may not have weight with them, it depends that the edges of the actual graph have weight or not. 

👉 The total number of spanning trees with n vertices that can be created from a complete graph is equal to n(n-2)

👉 if we have  n=4, the maximum number of possible spanning trees is equal to 44-2 = 16.  Thus, 16 spanning trees can be formed from a complete graph with 4 vertices.

Properties of Spanning Tree

• A connected graph can have multiple spanning trees. A graph with n vertices can have an n^(n-2) number of spanning trees.
• Spanning trees does not have any loop or cycle.
• Spanning trees have n vertices and n-1 number of edges. 
• All spanning tree of a graph has equivalent vertices. 
• Removing a single edge from the spanning tree will make the graph disconnected as the spanning tree is minimal connected. 
• Adding any edge can create a loop or cycle in the spanning tree. 
• Spanning trees can be formed on connected graphs only, disconnected graphs cannot form spanning trees. 

Example of Spanning Tree

Consider the following original graph:

The following Spanning trees are possible from the above graph:

Minimum Spanning Tree

A minimum spanning tree or minimum cost spanning tree is that spanning tree, which covers all the vertices of the graph with minimum edges and the sum of the weight of those edges is minimum among other spanning trees of that graph. 

Example of a Spanning Tree

The initial graph is:

Weighted graph

The possible spanning trees from the above graph are:

Minimum spanning tree - 1

Minimum spanning tree - 2

Minimum spanning tree - 3

Minimum spanning tree - 4

The minimum spanning tree from the above spanning trees is:

Minimum spanning tree

The minimum spanning trees are mainly of two types:

• Prim’s MST
• Kruskal’s MST

Prim’s MST

Prim’s algorithm starts with a single node/vertex and moves on to the adjacent vertices to explore all the connected edges. The idea behind prim’s algorithm is that it maintains two sets of vertices. The first set comprises vertices that are already included in the minimum spanning tree and the other set consists of all the vertices which are not included yet. 

How Prim's algorithm works

It falls under a class of algorithms called greedy algorithms that find the local optimum in the hopes of finding a global optimum.

We start from one vertex and keep adding edges with the lowest weight until we reach our goal.

The steps for implementing Prim's algorithm are as follows:

1. Initialize the minimum spanning tree with a vertex chosen at random.
2. Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree
3. Keep repeating step 2 until we get a minimum spanning tree

Example of Prim's algorithm

Start with a weighted graph

Choose a vertex

Choose the shortest edge from this vertex and add it

Choose the nearest vertex not yet in the solution

Choose the nearest edge not yet in the solution, if there are multiple choices, choose one at random

Repeat until you have a spanning tree

---

Kruskal’s MST

Kruskal’s algorithm is a greedy algorithm used to find out the shortest path in a minimum-spanning tree. The algorithm aims to traverse the graph and detect the subset of edges with minimal value and cover all the vertices of the graph. At every step of the algorithm and analysis, it follows a greedy approach for an overall optimized result. 

Kruskal’s algorithm can be summed up as a minimum spanning tree algorithm taking a graph as input and forms a subset of the edges of the graph, 

• which has a minimum sum of edge weight among all the trees that can be formed from that graph. 
• that form a tree including each vertex of the graph, without forming any cycle between the vertex.

How Kruskal's algorithm works

It falls under a class of algorithms called greedy algorithms that find the local optimum in the hopes of finding a global optimum.

We start from the edges with the lowest weight and keep adding edges until we reach our goal.

The steps for implementing Kruskal's algorithm are as follows:

1. Sort all the edges from low weight to high
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

Example of Kruskal's algorithm

Start with a weighted graph

Choose the edge with the least weight, if there are more than 1, choose anyone

Choose the next shortest edge and add it

Choose the next shortest edge that doesn't create a cycle and add it

Choose the next shortest edge that doesn't create a cycle and add it

Repeat until you have a spanning tree

---

Applications of Spanning Tree:

• In routing protocols
• Cluster mapping and analysis
• Network Planning
• Explore the path/ route in the maps.