# 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.![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI2F9QfycYm86IrhY%2Fhamiltonian%20path1.PNG?generation=1568003603038158\&alt=media)

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.

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI2FBS8aj3CfSfgAH%2Fhamiltonian%20path2.PNG?generation=1568003608526846\&alt=media)For vertex 0, dfs out and create a tree that represents all the possible paths from vertex 0.