Spanning Tree

Spanning Tree

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected..


  1. It is a connected tree
  2. It has no cycle
  3. Select all vertices (compulsory)
  4. Number of edges selected based on number given to the edges

So, Spanning Tree => AB (2) + BC(1) + CD(3)

=> 1+2+3

=> 6

Mathematical Properties of Spanning Tree
Spanning tree has n-1 edges, where n is the number of nodes (vertices).

From a complete graph, by removing maximum e – n + 1 edges, we can construct a spanning tree.

A complete graph can have maximum nn-2 number of spanning trees where n is the number of vertices in the graph

Suppose, if n = 4, the number of maximum possible spanning trees would be 54-2 = 25.

Thus, we can conclude that spanning trees are a subset of connected Graph G and disconnected graphs do not have spanning tree.

Application of Spanning Tree
Spanning tree is basically used to find a minimum path to connect all nodes in a graph. Common application of spanning trees are −

  • Civil Network Planning
  • Computer Network Routing Protocol
  • Cluster Analysis
  • Water-supply networks
  • Telecommunication networks, and electrical grids.

Minimum Spanning Tree (MST)
In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph. In real-world situations, this weight can be measured as distance, congestion, traffic load or any arbitrary value denoted to the edges.

Minimum Spanning-Tree Algorithm
Two most important spanning tree algorithms here − Both are greedy algorithms.

  • Kruskal’s Algorithm
  • Prim’s Algorithm
Kruskal’s AlgorithmPrim’s Algorithm
 Kruskal’s algorithm also follows greedy approach, which finds an optimum solution at every stage instead of focusing on a global optimumIt is a greedy algorithm that starts with an empty spanning tree.
This algorithm is also used to find the minimum spanning tree for a connected weighted graph. It is used to find the minimum spanning tree from the graph. 
Find the minimum spanning tree using Kruskal’s Algorithm

Step 1: Sort edge values

Step 2: Remove the Cyclic

Step 3: Draw edge with low weighted edge values

Step 4: Sum of all edge values
Find the minimum spanning tree using Prim’s Algorithm

Step 1: Start from Low weighted values from vertex

Step 2: Remove the Cyclic

Step 4: Sum of all edge values
Leave a Reply 0

Your email address will not be published. Required fields are marked *