DESIGN AND IMPLEMENTATION OF KRUSKAL'S MINIMUM SPANNING TREE ALGORITHM IN C++
The traditional algorithms (Prim) or (Kruskal) are able to obtain A minimum spanning tree (MST) in undirected graph easily. But many algorithms have been proposed for the purpose of obtaining spanning trees in undirected graph, these algorithms are considering the complexities of time and space. Some algorithms are generating spanning trees by using some basic cuts or circuits. In this process, the tree's cost is not considered. In this paper we will describe an algorithm for generating spanning trees in a graph of increasing cost, so we will get many possibilities, such as determining the k-th lowest spanning tree. The lowest spanning tree meets some additional constraints that may be found. We will discuss Murty's algorithm in this paper, which can find all solutions to assignment problem of increasing cost, and also discuss complexities of time and space.
Keywords: Performance Analysis, Computational Complexity, Graph, Minimum Spanning Trees.