Euclidean Minimum/Maximum Spanning Tree (EMST)
Today we are going to learn about Euclidean Spanning Tree problem, which is solved by using prim’s algorithm and not by kruskal’s. The idea behind the fact that the problem of euclidean maximum/minimum spanning tree is solved by prim’s is that the complexity of kruskal’s algorithm is (ElogE) where E is the no of edges, kruskal’s algorithm works fine for most of the general programming competition problems, but in case of Euclidean Spanning Tree. To understand that we have to first learn what is the need of this EMST.
Actually in euclidean MST problem all the ‘n’ points are connected to each other, and becomes the maximally dense graph. By virtue of that the order to compute the MST by using kruskal’s algo becomes (ElogE) where E = V^2 so order is greater than V^2 and in most cases the judges won’t accept it. So we can…
View original post 32 more words