What is a Spanning tree in Data Structure? | Data Structure Tutorial

In this article, you will learn about the Spanning tree and its types.

The two things we need to know before learning the spanning tree are undirected graphs and connected graphs. 

Undirected Graph: When the edges of the graph do not point in any direction it is known as an undirected graph. These edges are bidirectional also.

Connected Graph: It is a kind of graph in which there is always a path from a vertex to all other vertices.

Spanning Tree:

It is a combination of two graphs which is an undirected and connected graph. It consists of all the vertices of the graph with a minimum possible number of edges. If any of the vertices are connected, then definitely it is not a spanning tree. The weights may or may not be assigned with the edges. The total number of spanning trees with n vertices that are created from a complete graph is equal to n(n-2).

Minimum Spanning Tree:

A minimum spanning tree is a spanning tree in which the total of the edge's weight is as minimum as possible.

The minimum spanning Tree from a graph is found by using the following algorithms:

• Prim’s Algorithm
• Kruskal’s Algorithm

Applications of Spanning Tree

• Cluster Analysis
• Civil Network Planning
• Computer Network Routing Protocol.

Applications of Minimum Spanning Tree

• It helps in finding the paths on the map.
• It helps in designing the networks like telecommunication networks, electrical grids, and water supply networks.