Last Updated on September 22, 2023 by Mayank Dham
In this article, we are going to discuss the Spanning tree. This is one of the most important topics of data structure. First, we will study what is an undirected graph and a connected graph for a better understanding of the Spanning tree in Data Structures.
Undirected Graph
In the context of graph theory, an undirected graph is characterized by its edges lacking a designated direction, enabling traversal in either direction. These edges are bidirectional, implying that an edge linking vertex A to vertex B permits movement from vertex B to vertex A as well. It’s worth emphasizing that a directed graph stands in contrast, as its edges possess distinct directions, restricting traversal to those specified directions.
Connected Graph
A connected graph is a graph where there is a path between any two vertices. This means that for any two vertices in the graph, there is a sequence of edges that can be traversed to go from one vertex to the other.
In contrast, a disconnected graph is a graph where there is no path between some pairs of vertices, meaning that it is composed of two or more disconnected subgraphs.
Spanning tree
A spanning tree is a subgraph of an undirected, connected graph that includes all the vertices of the graph with a minimum possible number of edges. If a vertex is missing, it is not considered a spanning tree. The edges in a spanning tree may or may not have weights assigned to them.
The total number of spanning trees that can be formed from a complete graph with n vertices is equal to n(n-2). This can be calculated by using the formula where n is the number of vertices in the graph.
For instance, if the complete graph has 4 vertices, the maximum number of possible spanning trees is equal to 4(4-2) = 16. Therefore, it is possible to form 16 spanning trees from a complete graph with 4 vertices.
Its important to note that this is true for undirected graphs, directed graphs have different numbers of spanning trees can be created.
Its important to note that the above statement about the total number of spanning trees that can be created from a complete graph is only true for undirected graphs. In directed graphs, the total number of spanning trees that can be created from a complete graph is different.
In general, the concept of a spanning tree is useful when we want to have a simplified version of a graph while preserving its connectivity, it allows us to have a reduced representation of a complex network, reducing the number of edges while keeping the information about the connectivity between the vertices.
Example of a Spanning Tree
We can learn in detail about spanning trees by taking the following examples
Normal graph
Let the original graph be:
Given below are the possible spanning trees generated from the given graph:
Minimum Spanning Tree
In a minimum-spanning tree, the sum of the edges of the tree is the minimum possible value
Example of a Spanning Tree
We can understand the spanning tree by taking the following the example
The initial graph is:
Weighted graph
The possible spanning trees from the above graph are:
The minimum spanning tree from the above spanning trees is:
Minimum Cost Subgraph:
For all possible spanning trees, the minimum spanning tree must have the minimum weight possible. However, there may be other spanning trees with the same weight as the minimum-spanning tree, and those can also be considered Minimum Spanning Trees.
Minimum Cost Edge:
If the minimum cost edge of a graph is unique, it will be included in any Minimum Spanning Tree. For example, in the given figure, the edge AB (of least weight) is always included in MST.
If a new edge is added to the spanning tree, it will form a cycle because every spanning tree is minimally acyclic. In the given figure, adding edge AD or BC to the resulting MST would create a cycle.
The spanning tree is minimally connected, meaning if any edge is removed from the spanning tree, it will disconnect the graph. In the given figure, if any edge is removed from the resulting MST, it would disconnect the graph.
Algorithms for finding Minimum Spanning Trees include Kruskals and Prims algorithms.
The concept of MSTs was first introduced by Kruskal in 1956 and later by Prim in 1957. These algorithms have been developed to find the MST of a given graph.
Kruskals Algorithm
Kruskals algorithm starts by sorting all the edges of the graph in increasing order of their weights. Then, it takes each edge one by one and checks if adding the edge would create a cycle. If it doesn’t, the edge is added to the MST. This process is repeated until all the vertices of the graph are included in the MST.
Prims Algorithm
Prim’s algorithm, on the other hand, starts with an arbitrary vertex of the graph and adds to the MST all edges connecting the vertices that are already included in the MST to the vertices that are not yet included but have the minimum weight. This process is repeated until all the vertices are included in the MST.
Both Kruskals and Prims algorithms are used to find the MST of a graph. However, Kruskals algorithm is mainly used for graphs that are sparse, meaning the number of edges is much less than the number of vertices, and Prims algorithm is used for dense graphs, where the number of edges is close to the number of vertices.
In addition to MSTs, there are also other types of spanning trees such as the Maximum Spanning Tree (MaST) and the Shortest Path Tree (SPT). A MaST is a spanning tree with the largest possible total edge weight and SPT is a spanning tree that is used to find the shortest path from a specific vertex to all the other vertices in the graph.
Spanning trees are used in various fields such as computer networks, transportation systems, and image processing. In computer networks, spanning trees are used to create a loop-free topology, preventing network loops, and reducing the number of broadcast messages. In transportation systems, they are used to plan the most efficient routes, and in image processing, they are used to simplify the topology of a binary image while preserving its shape and connectivity.
Conclusion
spanning trees are a crucial concept in graph theory with many applications in various fields. The Minimum Spanning Tree (MST) is an important type of spanning tree that is used to find the subgraph with the smallest possible total edge weight. Kruskals and Prims algorithms are widely used to find the MST of a given graph. Other types of spanning trees such as Maximum Spanning Tree (MaST) and Shortest Path Tree (SPT) also have their own unique applications and uses.
Frequently Asked Questions (FAQs) about Spanning Tree in Data Structure
Below are the FAQs related to the Spanning tree in Data Structure:
1. What’s the significance of a spanning tree in Data Structure?
Spanning trees play a crucial role in ensuring network connectivity, optimizing network designs, and simplifying graph-related problems by reducing complexity.
2. How is a spanning tree different from a regular tree?
A spanning tree is derived from a graph and retains its connectivity while excluding cycles. A regular tree is a hierarchical data structure with a single root node and edges connecting parent and child nodes.
3. What’s the purpose of finding a minimum spanning tree in Data Structure?
A minimum spanning tree (MST) is a spanning tree with the lowest possible total edge weight. It’s used in scenarios where minimizing costs, such as in network design or resource allocation, is essential.
4. How can a spanning tree be constructed?
Various algorithms, such as Kruskal’s algorithm and Prim’s algorithm, can be employed to construct a spanning tree. These algorithms determine the optimal set of edges while avoiding cycles.
5. Can a graph have multiple spanning trees?
Yes, a graph can have multiple spanning trees if it has more than one valid set of edges that satisfy the conditions of a spanning tree.