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

Dec 18, 2022 #DataStructureTutorial, 239 Views

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

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.