Sunday, February 20, 2011

Prim's Algorithm

Greetings

Sometime back, I wanted to dive into a programming topic called graph theory. Graph theory is an extremely interesting topic in the sense one needs to use their brains to solve graph problems. Also many problems, such as the traveling salesman problem have only been partially solved at yet, making it a NP hard problem. I decided to start my dive with a lesson in Prim's Algorithm. However after countless hours of scourging the web, I could not find the code, nor an explanation simple enough for me to understand the algorithm. Thanks an awesome video I found on YouTube(I don't have the link, but I find it, I will post it here) on the Prim's Algorithm I was able to write my own interpretation of the Algorithm. This code makes use of arrays and simple vectors and is extremely easy to understand. I though of posting this code because I wanted anybody else in my position to be able to understand Prim's algorithm without having to resort to complex, unnecessary code. So what is the Prim' algorithm? Ever heard of problems such as the length of road required to connect all cities? or the cabling needed to form a network of computers, but some computers acting as proxies for the others? Well for all these problems, the MST or the minimum spanning tree has to be found. Imagine a group of cities (A to E) to be the nodes in a graph. Now imagine the distance between them to be the edges in a graph. Here is a pic.
An Example Graph
So the DIRECT distance from A to B is 10, A to E is 34, etc. However what is the least length of road to be constructed so that all the cities are connected? It is certainly not 106, the sum of all the distances. It happens to be 22 or the MST of the graph of cities. Try it out. cross out the distances of 33, 34 and 17 and you should still be able to travel from any city to any other city! Solving such problems require MST which can be found using the Prim's algorithm.The code I release for Prim's algorithm will have a detailed explanation on how it works. Here is a gist: start from any node, mark it visited. Choose the shortest path from all paths available and the add the path length to your MST counter. Get the node at the other end of the chosen path and mark that visited as well. Now considering the paths from all visited nodes, choose the shortest path and mark the node on the other end as visited. Continue to do this until all nodes are visited and once done you have the MST! The Prim's algorithm is great for finding the MST, although a little bit slower than other algorithms. However it is a simple algorithm to learn and is fun to work with. Links for the code and explanation down below. Once again you are free to modify and distribute the code with proper credit given.

Link to .exe file.
Link to code.

This is not the end...

Aravind Rao