# Spanning Tree in Data Structure

A spanning tree is a tree that connects all the vertices of a graph with the minimum possible number of edges. Thus, a spanning tree is always connected. Also, a spanning tree never contains a cycle. A spanning tree is always defined for a graph and it is always a subset of that graph. Thus, a disconnected graph can never have a spanning tree.

### Spanning Trees Terminologies:

1. Connected Graph: A connected graph is a graph in which we can reach any vertex from any vertex. Thus, in a connected graph, all vertices are connected to each other through at least one path.

2. Undirected Graph: It is a graph in which the edges don’t have a particular direction. In an undirected graph, the edges are bidirectional.

3. Directed Graph: In this case, the edges are unidirectional. Thus, we can go from only one end to the other ends. For every edge, there is an associated direction.

4. Simple graph: A simple graph is a graph that does not contain cycles and loops.

### Defining a Spanning Tree:

Every undirected and connected graph has a minimum of one spanning tree. Consider a graph having V vertices and E number of edges. Then, we will represent the graph as G(V, E). Its spanning tree will be represented as G’(V, E’) where E’ ⊆ E and the number of vertices remain the same. So, a spanning tree G’ is a subgraph of G whose vertex set is the same but edges may be different.

Example:
Consider the following undirected, simple and connected graph G having 4 vertices: A, B, C and D.

There are many spanning trees possible for this graph. Some of them are shown below:

The above graph G was a complete graph having 4 vertices. For any complete graph, the number of spanning trees is nn-2. Thus, in the worst case, the number of spanning trees formed is of the order O(n2).

### General Properties of Spanning Trees:

• There can be more than one spanning tree possible for an undirected, connected graph.
• In the case of directed graphs, the minimum spanning tree is the one having minimum edge weight.
• All the possible spanning trees of a graph have the same number of edges and vertices.
• A spanning tree can never contain a cycle.
• Spanning tree is always minimally connected i.e. if we remove one edge from the spanning tree, it will become disconnected.
• A spanning tree is maximally acyclic i.e. if we add one edge to the spanning tree, it will create a cycle or a loop.
• It is possible to have more than one minimum spanning tree if the graph weights of some edges are the same.
• Any connected and undirected graph will always have at least one spanning tree.

### Mathematical Properties of Spanning Trees:

• For any complete graph, the number of spanning trees is nn-2.
• In a complete graph, we can create a spanning tree by removing a maximum of E-N+1 edges. Here, E = Number of edges and N = Number of nodes/vertices.
• For a simple connected graph, its spanning tree will have N-1 edges, where N is the number of vertices.

### Minimum Spanning Tree:

A minimum spanning tree is defined for a weighted graph. A spanning tree having minimum weight is defined as a minimum spanning tree. This weight depends on the weight of the edges. In real-world applications, the weight could be the distance between two points, cost associated with the edges or simply an arbitrary value associated with the edges.

### Minimum Spanning Tree Algorithms:

There are various algorithms in computer science that help us find the minimum spanning tree for a weighted graph. Some of these algorithms are:

1. Prim’s Algorithm
2. Kruskal’s Algorithm
3. Both these algorithms follow the greedy approach to find the minimum cost spanning tree.

### Applications of Spanning Tree:

• For implementing Routing protocols in computer networks
• In civil network planning to build networks
• For clustering i.e. grouping similar objects under one category and distinguishing from other categories

### Applications of Minimum Spanning Tree:

• In designing telecommunication networks and water supply networks
• For finding paths in a map
• In electrical grid systems

### Conclusion:

In this article, we have seen what is a spanning tree and what is a minimum spanning tree. We have also seen their examples and applications. The article also covers the general as well as mathematical properties of spanning trees.

TechVidvan Team

The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today’s tech industry.