Abstract: Given an edge-weighted graph, a spanning tree of the graph is a tree containing all the vertices and some or all the edges. The minimum spanning tree (MST) or minimum weight spanning tree (MWST) problem calls for finding the spanning tree whose weight is less than or equal to the weight of every other spanning tree. In this paper, we have presented an algorithm for finding minimum spanning tree which is different from the traditional Kruskal’s and Prim’s algorithm. In this algorithm we transform the given graph into a forest and then the minimum spanning tree is obtained from the forest. We have also implemented the proposed algorithm and the Kruskal’s algorithm to find minimal spanning tree using Java programming language and the illustrations are demonstrated through a Java applet. We have presented some numerical examples to explain the solution procedure.
Keywords: Graph, Spanning Tree, Minimum Spanning Tree, Kruskal’s algorithm.
Title: Minimum Spanning Tree Algorithm
Author: D.Mishra, S.P.Behera, S. Bhattacharjee
International Journal of Computer Science and Information Technology Research
ISSN 2348-1196 (print), ISSN 2348-120X (online)
Research Publish Journals
