Kruskal's Algorithm Game

 


Kruskal's algorithm is an algorithm that is used to find a minimum spanning tree in a graph. It was discovered by computer scientist Joseph Kruskal, who published the result in his paper On the shortest spanning subtree of a graph and the traveling salesman problem (1956). The algorithm solves the problem of finding a minimum spanning tree by constructing a forest by greedily adding an 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 Kruskal's algorithm. Step by step you will have to choose an edge and grow your forest until the forest is a tree that 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 Kruskal's algorithm. For more details on Kruskal's algorithm, see the book Algorithm Design by Jon Kleinberg and √Čva Tardos.

Can you find the optimal solution?