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.