Spanning Tree – Meaning, Properties, Examples, and More

Have you ever wondered how complex network systems avoid loops and ensure efficient data pathways? Spanning tree, a concept in graph theory plays a crucial role in this process. It refers to a subset of a graph which includes all the vertices and is a tree, ensuring there are no cycles and the minimum number of edges to connect all nodes. Let's understand more!

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. A graph is a set of vertices and edges that are connected with each other, there are mainly three types of graphs, which are directed, undirected, and connected. A directed graph is also known as a digraph, the graph having edges between vertices along with defined directions is known as a directed graph. Undirected graphs do not have directions and the connected graph has each vertex connected with every other vertex present in the graph. 

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.

This blog covers the spanning tree, its properties, examples of the spanning tree, minimum spanning tree, and application of the spanning tree. 

Spanning Tree

The spanning tree is a subgraph of an undirected connected graph. It includes all the vertices in the subgraph and the least number of edges that can connect every vertex without forming a loop or cycle.  

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. 

Read on Complete Binary Tree

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. 

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. 

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.

Applications of Spanning Tree:

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