Real world applications where spanning tree data structure is used
Does anyone of you know any real world applications where spanning tree data structure is used?
Answer
In networking, we use Minimum spanning tree algorithm often. So the problem is as stated here, given a graph with weighted edges, find a tree of edges with the minimum total weight that satisfies these three properties: connected, acyclic, and consisting of |V| - 1 edges. (In fact, any two of the three conditions imply the third condition.)
as an example,
For instance, if you have a large local area network with a lot of switches, it might be useful to find a minimum spanning tree so that only the minimum number of packets need to be relayed across the network and multiple copies of the same packet don't arrive via different paths (remember, any two nodes are connected via only a single path in a spanning tree).
Other real-world problems include laying out electrical grids, reportedly the original motivation for Boruvka's algorithm, one of the first algorithms for finding minimum spanning trees. It shouldn't be surprising that it would be better to find a minimum spanning tree than just any old spanning tree; if one spanning tree on a network would involve taking the most congested, slowest path, it's probably not going to be ideal!
There are many other applications apart from the computer networks, i listed the references below:
Network design: – telephone, electrical, hydraulic, TV cable, computer, road The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn’t a tree you can always remove some edges and save money.
Approximation algorithms for NP-hard problems: – traveling salesperson problem, Steiner tree A less obvious application is that the minimum spanning tree can be used to approximately solve the traveling salesman problem. A convenient formal way of defining this problem is to find the shortest path that visits each point at least once.
Note that if you have a path visiting all points exactly once, it’s a special kind of tree. For instance in the example above, twelve of sixteen spanning trees are actually paths. If you have a path visiting some vertices more than once, you can always drop some edges to get a tree. So in general the MST weight is less than the TSP weight, because it’s a minimization over a strictly larger set.
On the other hand, if you draw a path tracing around the minimum spanning tree, you trace each edge twice and visit all points, so the TSP weight is less than twice the MST weight. Therefore this tour is within a factor of two of optimal.
Indirect applications: – max bottleneck paths – LDPC codes for error correction – image registration with Renyi entropy – learning salient features for real-time face verification – reducing data storage in sequencing amino acids in a protein – model locality of particle interactions in turbulent fluid flows – autoconfig protocol for Ethernet bridging to avoid cycles in a network
Cluster analysis: k clustering problem can be viewed as finding an MST and deleting the k-1 most expensive edges.
you can read the details from here, and here, and for a demo check here please.