1. There is an extended version of the nearest-neighbor algorithm in which you compare the total distances of the Hamiltonian circuits produced by applying the ordinary nearest-neighbor algorithm starting at each of the vertices of the graph (rather than just a specific one). Explore the effectiveness of this algorithm using the TSP: Nearest-Neighbor applet.

2. Go to the TSP: Sorted Edges applet, where you can apply the sorted-edges algorithm to see if it solves the traveling salesman problem for the following graphs (and others):

3. Go to the Kruskal’s Algorithm applet, where you can apply Kruskal’s algorithm to find the minimum-cost spanning trees in the following graphs (and others):