A graph is a finite set of dots and connecting links. The dots are called vertices (a single dot is a vertex), and the links are called edges. Each edge must connect two different vertices. A path is a connected sequence of edges showing a route on the graph that starts at a vertex and ends at a vertex. A circuit is a path that starts and ends at the same vertex. Circuits that visit each vertex once and only once are called Hamiltonian circuits.
Imagine now a graph where each edge is given a weight. This weight could be the distance or cost to get from one vertex to another. The sum of these weights for a given path is then the cost of that path. The problem of finding a Hamiltonian circuit with a minimum cost is often called the traveling salesman problem (TSP).
One strategy for solving the traveling salesman problem is the nearest-neighbor algorithm. Simply stated, when given a choice of vertices this algorithm selects the nearest (i.e., least cost) neighbor.
In our applet below your goal is to select a Hamiltonian circuit using the nearest-neighbor algorithm. To start your circuit click a vertex and drag the line to an adjacent vertex. Next select the vertex with least cost (closest). Continue in this way until you have completed a Hamiltonian circuit. The Reset button will clear the current path. The New Graph button will load a new graph.