In the previous post, we learn about the BFS i.e. Breadth-first Search.Today we are going to understand the application of it.Today we shall be analysing one of the applications of “Breadth-first search” traversal technique. We all know how important the concept of the tree is and how different traversal technique would help us in developing new and latest techniques.
Before we go any further we should first understand the basic concept of :
Whenever we want to reach a particular position we always choose the optimal path that is the shortest path it will not only reduce our travelling time but will also simplify our overall approach for doing a task.
A tree that contains all vertices in the graph.
The concept is relevant to connected undirected graphs.
Number of nodes in the spanning tree: |V|
Number of edges in the spanning tree: |V|-1
If the graph is unweighted any spanning tree will have the same number of edges. That is why it is not called “minimum” – all spanning trees will be ‘minimum’ trees with a number of edges equal to |V|-1.
If the graph is weighted then we are interested in finding a tree with a minimum total sum of the edge weights.
Consider it as a graph in which all the nodes will be null that is not numeric value at the junction there will be no weight.
Minimum Spanning Tree:
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Here no cyclic loop will be present and the sum of all weights i.e sum of all the nodes will be minimum.
Now we know the basic terminologies which are necessary to study the real world applications of our topic.
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
- Handwriting recognition
- Image segmentation