AN APPROACH TO GENERATE MST WITHOUT CHECKING CYCLE

Abstract

Abstract: A minimum spanning tree of an undirected graph can be easily obtained using classical algorithms by Prim or Kruskal. MST generation is a NP hard problem. Now this paper represents an algorithm to find minimum spanning tree without checking cycle. Good time and space complexities are the major concerns of this algorithm. Running Time (complexity) of this algorithm = O(E*log V) (E = edges, V = nodes),which is obviously better than prim’s algorithm(complexity- E +Vlog V) .  This algorithms operate at O(E * log(V)) time, though Prim’s can be optimized to O(E + V log V) by using specialized data structures(heap). For large graphs, these algorithms can take significant amount of time to complete. This algorithm is important in many real world applications. One example is an internet service provider determining the best way to install underground wires in a neighbourhood in order to use the least amount of wire and dig the least amount of ground.