Cheapest Link Algorithm

  1. Pick an edge with the cheapest weight, in case of a tie, pick whichever pleases you. Colour your edge.

  2. Pick the next cheapest uncoloured edge unless:
    1. your new edge closes a smaller circuit
    2. your new edge results in three coloured edges coming out of a single vertex. Again if there is a tie break it at your will.


  3. Repeat Step 2 until the hamilton circuit is complete.

Cheapest Link Algorithm Circuit

Here is how this algorithm works with our example.
  1. pick edge CE, weight 165. Mark it.

  2. pick edge AD, weight 185. Mark it.

  3. pick edge AC, weight 200. Mark it.

  4. jump edge AE, weight 205. It will result in three edges coming out of vertex A.

  5. jump edge ED, weight 302. It will close a small circuit.

  6. jump edge CB, weight 305. It will result in three edges coming out of vertex C.

  7. jump edge CD, weight 320. It will result in three edges coming out of vertex C.

  8. pick edge BE, weight 340. Mark it.

  9. pick edge BD, weight 360. Mark it.

  10. we have picked five edges we have to stop.

  11. calculate the weight of the circuit, i.e., add the weights of the five edges that were marked. This comes to 165 + 185 + 200 + 340 + 360 = 1250. This approximates the solution within 2.5% from the optimal answer of Brute-Force.

  12. exhibit the circuit. Our circuit is :A-D-B-E-C-A. The circuit is shown below.