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..
Rules:
- It is a connected tree
- It has no cycle
- Select all vertices (compulsory)
- 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 Algorithm | Prim’s Algorithm |
|---|---|
| Kruskal’s algorithm also follows greedy approach, which finds an optimum solution at every stage instead of focusing on a global optimum | It 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 |