Euclidean Minimum/Maximum Spanning Tree (EMST)

iCode

Hey folks,
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.
Problem
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

Advertisements

About Khuram Ali

Programming... Programming and Programming...!!!

Posted on June 3, 2013, in Algorithms and tagged , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: