[prev] 84 [next]

Hamiltonian Path and Circuit (cont)

Approach:
  • 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-1   (length = v for circuit)
    • resets "visited" marker after unsuccessful path