Hamiltonian Algorithms
Learn about Hamiltonian paths and cycles and how to find both in Python!
Start
Implementing Hamiltonian Algorithms in Python
Lesson 1 of 1
- 1We 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 Hamilt…
- 2Before we implement the Hamiltonian algorithm, let’s look at our starter code from the previous exercise closer. The information provided in this code will be our input data and will change dependi…
- 3We will create a custom Hamiltonian class responsible for traversing a graph to determine if a Hamiltonian path or cycle exists. When defining our Hamiltonian class, we should define the followin…
- 4The traversal search() method will be recursive, so we can backtrack and explore multiple paths within the graph. There are a few components for implementing this search: * The search() method sh…
- 5Once we have completed and recursively traversed a neighbor vertex, we should backtrack from that vertex to explore other paths and cycles that may exist in the graph. Backtracking allows us to f…
- 6Since the search() method is recursive, we need to provide an exit condition, otherwise we could end up in an infinite loop searching the graph. We should add this exit condition to the beginning o…
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory