Cheapest-Link
A C++ implementation of the cheapest-link heuristic for the Traveling Salesman Problem — building a near-optimal tour edge by edge.
The Traveling Salesman Problem is intractable to solve exactly at scale, so you reach for heuristics that get close, fast — and implementing them well is a real exercise in graph data structures.
I implemented the cheapest-link algorithm in C++: repeatedly add the lowest-cost edge that doesn’t create a vertex of degree three or a premature cycle, until a single Hamiltonian circuit forms.
Greedy edge selection
Sorts candidate edges by weight and adds them under the cheapest-link constraints (degree ≤ 2, no early cycles).
Tour assembly
Tracks partial paths and closes the final Hamiltonian circuit once enough edges are committed.
Heuristics live and die by their constraints. Most of the work was in the bookkeeping — detecting premature cycles and degree violations — not the greedy step itself.