Shortest Path and Minimum Spanning Tree for unweighted graph

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 :

Shortest Path:

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.

Shortest path using coderinme
Spanning Tree:

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.

Unweighted Graph:

unweighted Graph

 

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.

Minimum spanning tree using coderinem

 

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

 

Shortest Path and Minimum Spanning Tree for unweighted graph

A Salesforce Developer at AlmaMate Info Tech PVT LTD. An Aligarian and also your query solver in database field.This site mark the difference as Black or White to make you choose the best for you. Don't feel pressurized, feel confident..!!

Leave a reply:

Your email address will not be published.