An Efficient Greedy Minimum Spanning Tree Algorithm Based on Vertex Associative Cycle Detection Method

AbstractThe minimal spanning tree problem is a popular problem of discrete optimization. Numerous algorithms have been developed using the traditional approach but with the emergence of modern-day complex data structures, new algorithms have been proposed which are more complex yet asymptotically efficient. In this paper we present a cycle detection based greedy algorithm, to obtain a minimal spanning tree of a given input weighted undirected graph. The algorithm operates on the idea that every connected graph without any cycle is a tree. At successive iterations, the algorithm selects and tests if the highest degree vertex is a member of any cycle to remove the most expensive edge from the cycle associated with it. The iteration continues until all the cycles are eliminated to obtain the resultant minimal spanning tree. The simplicity of the algorithm makes it easier to understand and implement in any high-level languages. The proposed approach will be beneficial in analyzing certain class of problems in science and engineering