What is the shortest road network connecting every village?
You want to connect several villages with roads while keeping the construction cost as low as possible. Which pairs of villages should you connect so that "everything is connected with the minimum total length"? Click the canvas to place villages and find out for yourself.
Kruskal algorithm: Consider every possible road (pair of villages) from shortest to longest, one at a time. Discard a road that connects two villages already in the same connected group (because it would create a cycle), and accept only roads that connect villages not yet connected. It has been proven that this simple process always produces an optimal solution!
Accepted roads (Minimum Spanning Tree) Considered but rejected roads (would create a cycle)
Number of villages 0Total road length 0If every pair were connected 0
Click the canvas to place at least 5 villages (dots).