Given points on a plane, connect all of them so that every point can reach every other. The cost of an edge is the Manhattan distance, and you must minimise the total cost.
DSA Animator › DSA Revision › Graph › Min Cost to Connect All Points
Remember: connect everything cheaply means minimum spanning tree. On a dense graph, array based Prim beats sorting all edges. The video solves Min Cost to Connect All Points (LeetCode 1584, Medium) with the Minimum Spanning Tree pattern from the Graph topic, and you can replay every step in the interactive Min Cost to Connect All Points animation.
Given points on a plane, connect all of them so that every point can reach every other. The cost of an edge is the Manhattan distance, and you must minimise the total cost.
For the points 0 0, 2 2, 3 10, 5 2 and 7 0, the minimum total cost is 20.
Trying every set of n minus 1 edges is exponential. Connecting everything as cheaply as possible is a minimum spanning tree.
Use Prim’s algorithm, which grows one tree from a starting point. Keep, for every point outside the tree, the cheapest edge that connects it to the tree. Each step, add the outside point with the smallest such cost. Then update the costs of the remaining points using the new tree point. After n steps, the sum of the chosen costs is the answer.
Start the tree at point 0 0, with cost 0. The cheapest connection is 2 2, at distance 4. Next comes 5 2, at distance 3 from 2 2. Then 7 0, at distance 4 from 5 2. Finally 3 10, at distance 9 from 2 2. The total is 4 plus 3 plus 4 plus 9, which is 20.
In code, keep a best cost array filled with infinity, and an in tree array. Repeat n times: pick the point outside the tree with the smallest best cost, and add it. Add its cost to the total, and update the best cost of every other outside point. With this array version it's O of n squared, which is ideal for a complete graph.
Remember: connect everything cheaply means minimum spanning tree. On a dense graph, array based Prim beats sorting all edges.