Implementing Hamiltonian Algorithms in Python
Lesson 1 of 1
  1. 1
    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 Hamilt…
  2. 2
    Before 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…
  3. 3
    We 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…
  4. 4
    The 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…
  5. 5
    Once 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…
  6. 6
    Since 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…
  7. 7
    Congratulations! You’ve implemented the Hamiltonian algorithm to find both Hamiltonian paths and cycles within a graph! In this lesson, you have learned: * What a Hamiltonian path is * What a…

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo