Prim's Algorithm Game


Prim's algorithm is an algorithm that is used to find a minimum spanning tree in a graph. It was initially discovered in 1930 by mathematician Vojtěch Jarníkz, but is now known as Prim's algorithm due to computer scientist Robert Prim, who published the result in his paper Shortest connection networks and some generalizations (1957). The algorithm solves the problem of finding a minimum spanning tree by constructing a tree from a starting vertex by greedily adding an adjacent edge with minimum costs. Now it is your turn to solve this problem..

What do you have to do? You have to find the minimum spanning tree for the given graph by applying Prim's algorithm. Step by step you will have to choose an edge and grow your tree until the tree visits all vertices..

Important! It is possible to find the minimum spanning tree in multiple ways. However, you have to choose the solution that is obtained by using Prim's algorithm. For more details on Prim's algorithm, see the book Algorithm Design by Jon Kleinberg and Éva Tardos.

Give it a try! Can you find the optimal solution?