Study of Minimum Cost Spanning Tree Implementation on TSP based on complexities of Algorithm

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.