MST (Minimum Spanning Trees) is utilized in the Greedy technique to identify the cost or minimum path. Let T= (V’, E’) be a subgraph of the spanning tree G if and only if T is a tree, and G= (V, E) be an undirected connected graph.
Spanning trees are usually used to get an independent set of circuit’s equations in the electrical network. Once the spanning tree is obtained, suppose B is a set of edges not present in the spanning tree then adding one edge from B will form an electrical cycle.
A spanning tree is a minimal subgraph G’ of G such that V (G’) =V (G) and G’ is connected by a minimal subgraph. There must be at least n-1 edges in any connected graph with n vertices, and all connected graphs with n-1 edges are trees. G’s spanning trees will depict every possible option. The best-spanning tree is a tree with minimum cost.
The cost of the spanning tree is nothing but the sum of the cost of the edges in that tree. Any tree consisting of edges of a graph and including all the vertices of the graph is known as a “Spanning Tree”.
Fig 1: graph with vertices
The above figure shows a graph with four vertices and some of its spanning tree are shown below:
Fig 2: spanning-tree
Category of minimum spanning tree
There are two ways to do so:
Kruskal’s Algorithm: –
Here edges of the graph are considered in non-decreasing order of cost. The set of T edges so far selected for the spanning tree should be such that it is possible to complete T into a tree.
Prim’s Algorithm: –
Here the set of edges so far selected should form a tree. Now if A is the set of edges selected so far, then A has to form a tree. The next edge (u, v) to be added in A is the least costly edge that is not in A and has the property that A(u, v) also produces a tree.
Interested in learning about similar topics? Here are a few hand-picked blogs for you!
- What is the single-source shortest path?
- Explain binary search tree?
- What is Asymptotic notation?
- Illustrate greedy algorithm?
- What is recursion?