Algorithms · Animation

Prim’s Algorithm Progression Animation for randomly distributed points

For a given set of randomly distributed points in 2-dimensional space, Prim’s algorithm is utilized to find the minimum total distance from a randomly selected origin point (P_origin). Here, the progress of how the distances are selected by the algorithm at the first instant along the way to reach the minimum spanning tree (MST) is shown. The algorithm is written in C++, visualization is done via Python, video editing by Blender.

Also, for those who want to run their algorithm for the same set of points in this video, you can download the input files here: Dropbox path:

The input format is given below: (same as the UCSD Graphs course on Coursera):

  • First line is the total number of points, N
  • Then for the next N lines, we have two columns for x and y locations of points (x,y)
  • The first point is taken as the origin point
Input file format Sample input file
Npoints
x1 y1
...
xN yN
3
1 2
4 5
2 3

 Final minimum spanning tree snapshots for several random point distributions:

Minimum Spanning Trees as overlaid on West Coast of US and San Francisco region are also shown in the following figures. The geo-locations of the nodes are obtained from DIMACS and Python’s Basemap module is utilized for background maps.

usa_mst_withkruskal
Prim’s algorithm run on full US

Also using gmplot same MST plot overlaid on Google Maps:

sf_mst_gmaps
MST for San Francisco region overlaid on Google Maps via gmplot
For a similar animations on
If you have any questions or comments, please leave a note below. I would be happy to hear them.
Keywords:
Algoritmo de Prim, Алгоритм Прима, Algorithme de Prim, 普林姆算法
Advertisements

One thought on “Prim’s Algorithm Progression Animation for randomly distributed points

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