In the Greedy approach MST (Minimum Spanning Trees) is use to find the cost or the minimum path. Let G= (V, E) be an undirected connected graph, also T= (V’, E’) be a subgraph of the spanning tree G if and only if T is a tree.
Spanning trees (ST) are usually use to get an independent set of circuit’s equations in the electrical network. Once, it is obtain, suppose B is a set of edges not present in the ST then adding one edge from B will form an electrical cycle.
A ST is a minimal subgraph G’ of G such that V (G’) =V (G) and G’ is connect 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 tree with the minimum cost.
The cost of the ST is nothing but the sum of the cost of the edges in that tree. Any tree consisting the edges of a graph and including all the vertices of the graph is known as a “Spanning Tree”.
The above figure show a graph with four vertices and some of its are shown as below:
Minimum Cost Spanning Tree
Definition: Let G= (V, E) be an undirected connected graph. A sub-graph t= (V, E’) of G is a spanning tree of G iff t is a tree.
There are numerous applications for spanning trees. It can be used to generate a collection of circuit equations for an electric network that are independent of each other.
Further, In the Greedy approach a Minimum Cost Spanning Tree is creating using the given graph G. Consider the graph G, which is linked and weighted. The goal is to make a spanning tree T for G with the smallest possible sum of the weights of the tree edges in T.
To do so the greedy approach is to draw the tree by selecting edge by edge. Initially the first edge is select and then the next edge is select by considering the lowest cost. The process selecting edges one by one goes on till all the vertices have been visited with the edges of the minimum cost.
There are two ways to do so: –
Kruskal’s Algorithm: – Here edges of the graph are consider in non-decreasing order of cost. The set of T of edges so far selected for the this 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 from a tree. Now if A is the set of edges select so far, then A has to form a tree. The next edge (u, v) to be included in A is a minimum cost edge not in A with the property that A ∪{(u, v)} also results in a tree.
Interested in learning about similar topics? Here are a few hand-picked blogs for you!
- What is binary search tree?
- Illustrate computer networking?
- What is DBMS?
- Define semaphore?
- What is constructor?