We have just reviewed Hamiltonian algorithms. As a reminder, the algorithm consists of two parts:
- A Hamiltonian path: a path in a graph that visits each vertex (or node) exactly once.
- A Hamiltonian cycle (or circuit): contains a Hamiltonian path and the starting and ending vertices are the same.
There are several ways to determine if a Hamiltonian path or cycle exists in a graph programmatically. The method we will be implementing in this lesson is a brute force approach in Python. This approach allows us to visit every vertex and its connected, neighboring vertices recursively. We can then backtrack out to traverse the next unvisited vertex to see if more paths or cycles exist, until we have visited all vertices.
As we move through implementing the algorithm, it may be helpful to consider how we can use this algorithm in a real-world scenario. Take a look at the graph to the right. A school district could try to find Hamiltonian cycles when mapping out bus stops between students’ houses. This would allow for finding the most efficient bus route that visits each student’s house exactly once.
Looking at the graph to the right, how can we implement a program to programmatically traverse the graph to determine if one or more Hamiltonian paths and cycles exist? The following exercises will walk through this implementation.
Review the following starter code to get started.