Hamiltonian Path

A Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once. If a Hamiltonian path exists whose endpoints are adjacent, then the resulting graph cycle is called a Hamiltonian cycle (or Hamiltonian cycle).

To give a better understanding of the problem consider the following 3 graphs.

While figure 1 does not contain an Hamiltonian Path, figure 2 contains 2 Hamiltonian paths as depicted in figures 3 and 4.

In general, the problem of finding any Hamiltonian Path in a graph is an NP-complete problem, but there are different levels of efficiency we can still go about solving this problem.

Approach 1: Permutations

1. Generate all permutation of vertices in the graph.

2. For each permutation, confirm whether or not it is a valid path. A path is valid if from vertex A_i to A_i+1, A_i has an edge to A_i+1 and there are a total of i=N vertices in the path.

The time complexity for this algorithm is O(N*N!). N! to generate every permutation, and an additional N to check each one.

Approach 2: Back Tracking [implemented]

This algorithm is technically still brute force, but it is a smarter way of approaching things. Essentially, what we do is find all all paths in a graph from a starting vertex. If a path is valid, then we've found a Hamiltonian path. As a short example, look at the image below.

For vertex 0, dfs out and create a tree that represents all the possible paths from vertex 0.