AN APPROACH TO GENERATE MST WITHOUT CHECKING CYCLE
Keywords:MST(Minimum spanning tree)
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.