• Dillip Narayan Sahu

A spanning tree is a sub-graph of a graph G which contains all vertices and contains no circles. A graph can have multiple spanning trees. We can also assign some weight/value/cost to each edge of the graph. The minimum cost spanning tree will be the lowest cost spanning tree among different spanning trees of the graph G. This paper presents a fast and efficient algorithm for the construction of minimum cost spanning trees (MCST) based on the concept of Travelling Salesman problem (TSP) in a connected weighted graphs G. The algorithm incorporates the traditional method to sort the weights / costs associated with the edges in the graph G in linear time. Also the algorithm exploits the fact that every connected graph G with "n" number of nodes with exactly "n-1" number of edges is a tree. The complexity of the algorithm is bounded by Big-O(m log n ), where m is the number of edges and n is the number of vertices of the graph G. Our objective is to find the minimum cost spanning tree in a graph G and use that concept on a traveling salesman problem (TSP) based on complexities of algorithm.

Complexity, MCST, Simple Graph, TSP, Weighted Graph.

"Study of Minimum Cost Spanning Tree Implementation on TSP based on complexities of Algorithm", International Journal of Emerging Technologies and Innovative Research (www.jetir.org), ISSN:2349-5162, Vol.8, Issue 8, page no.d882-d891, August-2021, Available :http://www.jetir.org/papers/JETIR2108478.pdf

"Study of Minimum Cost Spanning Tree Implementation on TSP based on complexities of Algorithm", International Journal of Emerging Technologies and Innovative Research (www.jetir.org | UGC and issn Approved), ISSN:2349-5162, Vol.8, Issue 8, page no. ppd882-d891, August-2021, Available at : http://www.jetir.org/papers/JETIR2108478.pdf