Goseeko blog

What is a Minimum Spanning Tree?

by Bhumika

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!

You may also like