Did you know that in a Local Area Network, the spanning tree data structure is applied to manage routing systems? Additionally, it is also used to implement telecommunication networks, transportation networks, and electrical grids as it provides an optimal implementation path. So, in this article, we will discover what a spanning tree in data structure is and understand its functionalities and applications.
Graphs and Their Different Types
Spanning tree in data structures and algorithms is developed by referencing the mathematical field of graph theory. Thus, primarily, we shall understand a few terminologies about the graph at a glance.
A graph is a structure that contains vertices and edges connecting them. Based on their edge connectivity, there are three basic types of graphs as follows:
-
Undirected Graph
The graph in which all the edges don’t point to any specific direction is called an undirected graph. Since there is no particular direction given for traversal, this graph’s edges are considered bidirectional. The representation of the graph shown below is an example of an undirected graph.
-
Directed Graph
The graph in which all the edges point to only one specific direction is called a directed graph. In this type of graph, the retrieval to the last node is not possible since the edges of this graph can only be traversed in one direction.
In the diagram shown above, you can clearly observe that the traversal is possible from direction A -> E.However, you cannot retrieve back at position A from node E due to the directions of edges.
-
Connected Graph
A connected graph is a graph in which there is a path from one vertex to any other vertex in a graph. According to this definition, null graphs and singleton graphs can also be called connected graphs. The graph shown below is a connected graph, as you can visit any vertex from any other vertex of a graph.
Introduction to Spanning Tree
If you have graph G with vertices V and edges E, then that graph can be represented as G(V, E). For this graph G(V, E), if you construct a tree structure G’(V’, E’) such that the formed tree structure follows constraints mentioned below, then that structure can be called a Spanning Tree.
- V’ = V (number of Vertices in G’ must be equal to the number of vertices in G)
- E’ = |V| - 1 (Edges of G’ must be equal to the number of vertices in graph G minus 1)
Let’s understand this by creating spanning trees for a particular graph structure.
Creating Spanning Trees for Given Graph
Let’s assume that you want to create the spanning tree structures for the graph given below:
As mentioned earlier, the spanning tree has the same number of vertices as the graph. In this case, you have a total number of vertices in the graph equal to 5. Thus, T(V’, E’) will also have 5 vertices in its structure. Additionally, the number of edges E’ must be equal to the number of vertices in the graph minus one, i.e., 4. For this given graph, five spanning trees can be constructed as shown below:
How to Calculate the Number of Possible Spanning Trees
A connected graph can have several spanning trees, as previously stated. So, how do you estimate how many distinct spanning trees can be created for a given graph? Graph theory in mathematics provides the answer to this question. According to graph theory, in order to determine the number of feasible spanning trees, you must first determine the graph's type.
If a given graph formulates a closed cycle and has the number of vertices equal to the number of edges, then that graph can be called a cycle graph. And the number of possible spanning trees for any cycle graph is equal to the number of its vertices or edges. The graph for which we created the spanning trees previously had 5 vertices and 5 edges with a closed cycle.
Thus, n(ST)cycle graph =V =E =5
Otherwise, if a unique edge connects each pair of vertices in a graph, it will be considered as a complete graph. And the number of possible spanning trees for this complete graph can be calculated using Cayley’s Formula:
n(ST)complete graph =V(v-2)
The graph given below is an example of a complete graph consisting of 4 vertices and 6 edges. For this graph, number of possible spanning trees will be:
n(ST)cg =V(v-2)=4(4-2)=42=16
Properties of Spanning Tree
In parallel and distributed computing, spanning trees are crucial. Listed below are a few important properties of spanning trees.
- A spanning tree whose overall resultant weight value is minimal is considered to be a Minimal Spanning Tree.
- A connected graph can have more than one spanning tree.
- All Spanning trees must contain the same number of vertices as of graph, and the number of edges must be equal to |V| - 1.
- The spanning tree must not contain any cycle.
- If the given graph is a cycle graph, then the number of possible spanning trees will be equal to the number of vertices of the given graph.
- If the given graph is a complete graph, then the number of possible spanning trees can be calculated using Cayley’s Formula.
- A spanning tree cannot be disconnected. If you remove any edge from the created tree, then it won’t be considered as a spanning tree anymore. It can only be regarded as a disconnected graph. The diagram given below explains the same:
- There is a chance that there will be more than one minimum spanning tree if there are numerous edges with the same weight.
Consider the example given below. The graph shown here has 4 vertices and 4 edges. And two edges of this graph have the same weight values as the remaining two. Thus, the possible spanning trees for this graph will be more than one with the exact cost.
Applications of Spanning Tree
The following are the applications of the spanning trees:
- Telecommunication Network Building: If we want to develop a telecommunication network for the entire city, a basic naive approach will be more expensive. We can create a communications system at a lower cost by using the Minimum Spanning Tree technique. The image given below explains the difference between Naive and MST routing.
- Constructing Highways or Railroads: For constructing highways or railroads the Minimum Spanning Tree approach is utilized everywhere. Given the possible routes between two cities, MST technique provides you with the optimal route. Basically, the algorithm treats the cities as the vertices and paths joining them as edges to create a subtree that will make the route fully connected and cost efficient.
- Image Segmentation: During picture segmentation, a spanning tree is utilized to construct tiles of comparable pixels. The pixels which seem closer to each other and have the same color type are grouped together. This technique is used in every aspect of computer vision in machine learning.
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Conclusion
In this tutorial, we explored Spanning Tree in a data structure. We discussed various properties of spanning trees and learned how to create these trees for a given graph topology. Later, in this tutorial, we also learned about the applications of spanning trees in order to comprehend its significance.
If you are looking for more extensive learning that goes beyond data structures and covers the principles of interactive application development, Simplilearn’s Software Development Courses will prove to be precisely suitable for you. The courses listed in the catalog above will assist you in mastering the craft of software development and prepare you for employment. Explore now and get started!
Have any questions about this article? If yes, please leave them in the comments section at the bottom of this page; we will respond to them soon!
