Hamilton Path and Tour (cont)
Approach (generate-and-test):
- generate all possible simple paths (using e.g. DFS)
- keep a counter of vertices visited in current path
- stop when find a path containing V vertices
Can be expressed via a recursive DFS algorithm
- similar to simple path finding approach, except
- keeps track of path length; succeeds if length = v
- resets "visited" marker after unsuccessful path
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}