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:
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.
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.
Here's How to Land a Top Software Developer Job
Full Stack Development-MEANExplore Program
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:
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.
Stand Out From Your Peers this Appraisal Season
Start Learning With Our FREE CoursesEnroll Now
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 theFull Stack Web Developer - MEAN Stack Master's Program. Enroll now!
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!
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.. By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree.What is an example of a spanning tree in real life? ›
A minimum spanning tree is a special kind of tree that minimizes the lengths (or “weights”) of the edges of the tree. An example is a cable company wanting to lay line to multiple neighborhoods; by minimizing the amount of cable laid, the cable company will save money. A tree has one path joins any two vertices.What is spanning tree simple? ›
A spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible number of edges. If a vertex is missed, then it is not a spanning tree. The edges may or may not have weights assigned to them.What is a spanning tree Why are they useful? ›
The Spanning Tree Protocol (STP) is a network protocol that builds a loop-free logical topology for Ethernet networks. The basic function of STP is to prevent bridge loops and the broadcast radiation that results from them.What is considered a spanning tree? ›
A spanning tree is a connected graph using all vertices in which there are no circuits. In other words, there is a path from any vertex to any other vertex, but no circuits. Some examples of spanning trees are shown below.What is a spanning set example? ›
Definition. A subset S of a vector space V is called a spanning set for V if Span(S) = V. Examples. (x,y,z) = xe1 + ye2 + ze3.What are three examples of how minimum spanning trees can be used in real life applications? ›
Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids (which they were first invented for, as mentioned above).What are the different types of spanning tree? ›
Types of STP are Rapid Spanning Tree Protocol, virtual LAN, Per VLAN spanning tree, Per VLAN Rapid spanning tree, Multiple Spanning Tree Protocol, etc. Stages of RSTP are forwarding, blocking, learning, listening, and disabled state. RSTP provides loop-free topology in the Ethernet network.What is the difference between spanning tree and spanning tree? ›
A tree is a connected graph that contains no cycles, multiple edges or loops. A spanning tree represents a connection between all vertices without certain edges which are usually less-optimal in length.Which spanning tree is best? ›
802.1w – Rapid Spanning Tree Protocol (RSTP) – It is a spanning standard developed by IEEE which provides faster convergence than CST but holds the same idea of finding a single root bridge in the topology. The bridge resources needed in RSTP is higher than CST but less than PVST+ . Advantages: Prevents network loops.
Definitions. A tree is a connected undirected graph with no cycles. It is a spanning tree of a graph G if it spans G (that is, it includes every vertex of G) and is a subgraph of G (every edge in the tree belongs to G).What are the advantages of spanning tree in data structure? ›
Advantages: Spanning trees are used to avoid or prevent broadcast storms in spanning tree protocol when used in networks. This is also used in providing redundancy for preventing undesirable loops in the spanning tree or network.What is spanning tree in networking with example? ›
Spanning Tree Protocol (STP) is a Layer 2 network protocol used to prevent looping within a network topology. STP was created to avoid the problems that arise when computers exchange data on a local area network (LAN) that contains redundant paths.Where are spanning trees used? ›
Spanning trees are important in path-finding algorithms such as Dijkstra's shortest path algorithm and A* search algorithm. Spanning trees are calculated as sub-parts in those algorithms. It is also used in network routing protocols.Which simple graphs have spanning tree? ›
Therefore, a connected simple graph has exactly one spanning tree.What are some examples of why we might want to find a minimum spanning tree for a graph? ›
Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching. Other practical applications are: Cluster Analysis.