• REVIEW OF MINIMUM SPANNING TREE IN AN UNDIRECTED GRAPH

Abstract

A Minimum spanning tree of a weighted graph is a tree having all vertices of a given graph with weight less than or equal to the weight of all such possible spanning trees from the given graph. In this paper we propose new method and corresponding algorithm to construct a minimum spanning tree of a weighted graph. This new approach is based on Edge Elimination Method. In this method we eliminate an edge with highest weight in each of the smallest cycle of the weighted graph until no cycle is remained in the graph with care that graph is not disconnected at any stage. Once such a graph (tree) is obtained it is the required minimum spanning tree in an undirected weighted graph.