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 depending on what graph we are testing with, so this data does not need to be a part of our custom Hamiltonian class. In our test graph, we have vertices labeled “School”, “Sanjay”, “Marquis”, “Marisol”, and “Lisa”. Each vertex has an assigned index from 0 to 4, respectively.
Our input data provides:
vertices: a list of vertices (nodes) that are in the graph
adjacency_matrix: matrix, or nested lists, that represents the adjacency matrix of the graph.
The adjacency matrix tells us what vertices are connected to which. In the matrix:
- a 1 indicates that the vertices are connected, and
- a 0 indicates that they are not connected.
Our input data provides the following adjacency matrix. In this matrix, the numbers in the parentheses will represent the index for that student. So, when we access
adjacency_matrix, we retrieve a list of all values in that column, or
[1, 0, 1, 0, 0].
To understand this matrix, let’s look at vertex “School”. “School” is connected to “Sanjay”, index 1 and “Lisa”, index 4 since it has values 1 for each of these vertices. Since “School” is not connected to any other vertex, it has 0 for all other vertices. To learn more about adjacency matrices, click here.
Now that we have a better understanding of the starting code, we are ready to implement the Hamiltonian algorithm to find all Hamiltonian paths and cycles!
Review the adjacency matrix to understand how we determine which vertices are connected to each other.