Prim’s Algorithm Progression Animation for randomly distributed points (original) (raw)

Skip to content

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

Final minimum spanning tree snapshots for several random point distributions:

Another MST

For another set of points

For 500 points

Minimum Spanning Tree using Prim’s Algorithm

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.

Minimum Spanning Tree for San Francisco and vicinity

Minimum Spanning Tree over West of United States

Prim’s algorithm run on full US

Also using gmplot same MST plot overlaid on Google Maps:

MST for San Francisco region overlaid on Google Maps via gmplot

For a similar animations on

• Kruskal’s algorithm, check this page.
• Dijkstra’s algorithm, check here

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, 普林姆算法