Hamiltonian circuits : Sorted-edges algorithm - Basic question PLS HELP ASAP?

Question

We're doing nearest-neighbor and sorted-edges algorithms in class, but what I don't understand is the sorted-edges algorithm. Isn't it the same as the nearest neighbor algorithm when started from the smallest edge?

Answer 1

The difference between the two is that the sorted-edges algorithm looks at the whole set of edges each time, not just the one connected to the last vertex.

So if you had a shape like the following (bad example)

A --- 2 --- B
| ............... |
5 ............. 8
| ............... |
C --- 3 --- D

You would take side AB, then you would add CD to the set of edges. Notice they are disjoint. Imagine a few diagonals, or more vertices and you may get different results with the two algorithms.

Does that make sense?

Answer 2

Sorted Edges Algorithm