{"id":6536,"date":"2021-09-28T12:48:51","date_gmt":"2021-09-28T07:18:51","guid":{"rendered":"https:\/\/www.goseeko.com\/blog\/?p=5731"},"modified":"2021-09-28T12:48:51","modified_gmt":"2021-09-28T07:18:51","slug":"what-is-a-minimum-spanning-tree","status":"publish","type":"post","link":"https:\/\/www.goseeko.com\/blog\/what-is-a-minimum-spanning-tree\/","title":{"rendered":"What is a Minimum Spanning Tree?"},"content":{"rendered":"\n

MST (Minimum Spanning Trees<\/a>) 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.<\/p>\n\n\n\n

Spanning trees are usually used to get an independent set of circuit\u2019s 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. <\/p>\n\n\n\n

A spanning tree is a minimal subgraph G\u2019 of G such that V (G\u2019) =V (G) and G\u2019 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.\u00a0<\/p>\n\n\n\n

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 \u201cSpanning Tree\u201d.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Fig 1: graph with vertices   <\/p>\n\n\n\n

The above figure shows a graph with four vertices and some of its spanning tree are shown below:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n

Fig 2: spanning-tree<\/p>\n\n\n\n

Category of minimum spanning tree<\/strong><\/h2>\n\n\n\n

There are two ways to do so:<\/p>\n\n\n\n

Kruskal\u2019s Algorithm: – <\/strong><\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Prim\u2019s Algorithm: – <\/strong><\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Interested in learning about similar topics? Here are a few hand-picked blogs for you!<\/strong><\/p>\n\n\n\n