What is a Hamiltonian Path?
A Hamiltonian path is similar to a Hamiltonian cycle, but instead of forming a closed loop, it is a path that visits each vertex in the graph exactly once without returning to the starting vertex.
The key properties of a Hamiltonian path are:
1. Visits every vertex in the graph exactly once
2. Does not return to the starting vertex
3. The graph must be connected for a Hamiltonian path to exist
Let's consider the same example graph from before with 4 vertices A, B, C, & D. An example of a Hamiltonian path (but not a cycle) in this graph would be: A -> B -> C -> D. This path visits each vertex once but does not loop back to A.
Every Hamiltonian cycle is also a Hamiltonian path, but not every Hamiltonian path is a cycle. If a graph has a Hamiltonian cycle, it must also have a Hamiltonian path. However, a graph with a Hamiltonian path may or may not have a cycle.
Finding Hamiltonian paths is also an NP-complete problem, just like finding Hamiltonian cycles. But for small graphs, we can use algorithms like backtracking to find paths & cycles efficiently.
Hamiltonian Cycle using Backtracking Algorithm
Now that we understand what Hamiltonian cycles are, let's see how we can find them in a graph using a backtracking algorithm.
Backtracking is a general algorithmic technique that explores all possible solutions by incrementally building candidates to the solution and abandoning a candidate ("backtracking") as soon as it determines that the candidate cannot lead to a valid solution.
Here's how we can apply backtracking to find Hamiltonian cycles:
1. Start with an empty path and choose any vertex as the starting point.
2. Add the starting vertex to the path.
3. Recursively build the path by choosing the next unvisited vertex and adding it to the path.
4. If the path contains all vertices and the last vertex has an edge to the starting vertex, we have found a Hamiltonian cycle.
5. If the path does not meet the criteria for a Hamiltonian cycle, backtrack by removing the last vertex from the path and trying a different unvisited vertex.
6. Continue this process until a Hamiltonian cycle is found or all possibilities have been exhausted.
The backtracking algorithm explores all possible paths in the graph and finds a Hamiltonian cycle if one exists. If no Hamiltonian cycle is found after exploring all paths, the graph does not have one.
Here is the pseudocode for the backtracking algorithm to find a Hamiltonian cycle:
function findHamiltonianCycle(graph, path, visited):
if path contains all vertices and last vertex has edge to first vertex:
return path
for each unvisited neighbor vertex v of the last vertex in path:
add v to path
mark v as visited
recursively call findHamiltonianCycle(graph, path, visited)
if a Hamiltonian cycle is found:
return path
remove v from path
mark v as unvisited
return no Hamiltonian cycle found
This algorithm recursively explores all possible paths and backtracks when a path does not lead to a Hamiltonian cycle. The time complexity of this brute-force approach is O(n!), where n is the number of vertices, as it explores all permutations of vertices. The space complexity is O(n) for the recursion stack.
Illustrations
Let's see how the backtracking algorithm works to find a Hamiltonian cycle in an example graph. Consider the following undirected graph with 4 vertices:
B -- C
/ \ /
A---D
We start at vertex A and recursively explore all possible paths:
1. Path: [A]
Unvisited neighbors: B, D
Choose B, Path: [A, B]
2. Path: [A, B]
Unvisited neighbors: C, D
Choose C, Path: [A, B, C]
3. Path: [A, B, C]
Unvisited neighbors: D
Choose D, Path: [A, B, C, D]
4. Path: [A, B, C, D]
All vertices visited & last vertex D has an edge to starting vertex A
Hamiltonian cycle found: [A, B, C, D, A]
In this example, the algorithm finds the Hamiltonian cycle [A, B, C, D, A]. If we had chosen a different sequence of vertices, like [A, D, C, B], it would have also led to a valid Hamiltonian cycle.
Now let's look at another example where the graph does not have a Hamiltonian cycle:
B---C
/
A---D
1. Path: [A]
Unvisited neighbors: B, D
Choose B, Path: [A, B]
2. Path: [A, B]
Unvisited neighbors: C
Choose C, Path: [A, B, C]
3. Path: [A, B, C]
Unvisited neighbors: D
Choose D, Path: [A, B, C, D]
4. Path: [A, B, C, D]
All vertices visited but last vertex D does not have an edge to starting vertex A
Backtrack & remove D from path
5. Path: [A, B, C]
No more unvisited neighbors
Backtrack & remove C from path
6. Path: [A, B]
No more unvisited neighbors
Backtrack & remove B from path
7. Path: [A]
Choose D, Path: [A, D]
8. Path: [A, D]
No unvisited neighbors that can lead to a Hamiltonian cycle
Backtrack & remove D from path
9. Path: [A]
No more unvisited neighbors
No Hamiltonian cycle found
In this case, the algorithm explores all possible paths but does not find a Hamiltonian cycle because one does not exist in the graph.
Implementation
Now let's see how to implement the backtracking algorithm to find Hamiltonian cycles in code.
Python
def hamiltonian_cycle(graph, path, visited):
if len(path) == len(graph) and graph[path[-1]][path[0]] == 1:
path.append(path[0])
return path
for v in range(len(graph)):
if graph[path[-1]][v] == 1 and not visited[v]:
visited[v] = True
path.append(v)
result = hamiltonian_cycle(graph, path, visited)
if result is not None:
return result
visited[v] = False
path.pop()
return None
# Example usage
graph = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]
visited = [False] * len(graph)
path = [0]
visited[0] = True
cycle = hamiltonian_cycle(graph, path, visited)
print(cycle)
You can also try this code with Online Python Compiler
Java
public class HamiltonianCycle {
public static List<Integer> hamiltonianCycle(int[][] graph, List<Integer> path, boolean[] visited) {
if (path.size() == graph.length && graph[path.get(path.size() - 1)][path.get(0)] == 1) {
path.add(path.get(0));
return path;
}
for (int v = 0; v < graph.length; v++) {
if (graph[path.get(path.size() - 1)][v] == 1 && !visited[v]) {
visited[v] = true;
path.add(v);
List<Integer> result = hamiltonianCycle(graph, path, visited);
if (result != null) {
return result;
}
visited[v] = false;
path.remove(path.size() - 1);
}
}
return null;
}
public static void main(String[] args) {
int[][] graph = {
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
boolean[] visited = new boolean[graph.length];
List<Integer> path = new ArrayList<>();
path.add(0);
visited[0] = true;
List<Integer> cycle = hamiltonianCycle(graph, path, visited);
System.out.println(cycle);
}
}
You can also try this code with Online Java Compiler
C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> hamiltonianCycle(vector<vector<int>>& graph, vector<int>& path, vector<bool>& visited) {
if (path.size() == graph.size() && graph[path.back()][path[0]] == 1) {
path.push_back(path[0]);
return path;
}
for (int v = 0; v < graph.size(); v++) {
if (graph[path.back()][v] == 1 && !visited[v]) {
visited[v] = true;
path.push_back(v);
vector<int> result = hamiltonianCycle(graph, path, visited);
if (!result.empty()) {
return result;
}
visited[v] = false;
path.pop_back();
}
}
return {};
}
int main() {
vector<vector<int>> graph = {
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
vector<bool> visited(graph.size(), false);
vector<int> path = {0};
visited[0] = true;
vector<int> cycle = hamiltonianCycle(graph, path, visited);
for (int v : cycle) {
cout << v << " ";
}
cout << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output
0 1 2 3 0
Time & Space Complexity
Let's analyze the time and space complexity of the backtracking algorithm for finding Hamiltonian cycles.
Time Complexity
The backtracking algorithm explores all possible paths in the graph, which results in a time complexity of O(n!), where n is the number of vertices in the graph. This is because there are n! possible permutations of the vertices, and in the worst case, the algorithm explores all of them.
At each recursive call, the algorithm checks if the current path is a Hamiltonian cycle and then explores all unvisited neighboring vertices. The number of recursive calls is equal to the number of possible paths, which is n!.
Since the algorithm uses an adjacency matrix representation of the graph, checking if an edge exists between two vertices takes constant time O(1). The total number of edge checks is O(n) for each path.
Therefore, the overall time complexity is O(n * n!) = O(n!), which is exponential in the number of vertices. This makes the algorithm inefficient for large graphs, as the time complexity grows factorially with the number of vertices.
Space Complexity
The space complexity of the backtracking algorithm is O(n) because it uses additional data structures to keep track of the current path and visited vertices.
The recursion stack also contributes to the space complexity. In the worst case, the recursion depth can be equal to the number of vertices n, as the algorithm explores all possible paths. Each recursive call adds a new frame to the stack, storing the local variables and function arguments.
The space required for the adjacency matrix representation of the graph is O(n^2), where n is the number of vertices. However, this space is used to store the input graph and is not considered as extra space used by the algorithm.
So, the overall space complexity of the backtracking algorithm for finding Hamiltonian cycles is O(n), where n is the number of vertices in the graph.
Note: It's important to note that the exponential time complexity makes this algorithm impractical for large graphs. For such cases, more efficient algorithms or approximation techniques are used to find Hamiltonian cycles or determine their existence.
Frequently Asked Questions
Can a graph have multiple Hamiltonian cycles?
Yes, a graph can have multiple Hamiltonian cycles. The number of distinct Hamiltonian cycles depends on the structure of the graph.
Is every Hamiltonian cycle also an Eulerian cycle?
No, not every Hamiltonian cycle is an Eulerian cycle. An Eulerian cycle visits every edge exactly once, while a Hamiltonian cycle visits every vertex exactly once.
Can a disconnected graph have a Hamiltonian cycle or path?
No, a disconnected graph cannot have a Hamiltonian cycle or path. By definition, a Hamiltonian cycle or path must visit all vertices, which is impossible if the graph is not connected.
What are the rules for Hamiltonian path?
A Hamiltonian path visits each vertex of a graph exactly once. The path may start and end at different vertices, and no vertex is repeated. Not all graphs have Hamiltonian paths.
Conclusion
In this article, we discussed the concepts of Hamiltonian cycles and paths in graph theory. We learned that a Hamiltonian cycle is a closed loop that visits every vertex exactly once, while a Hamiltonian path visits every vertex exactly once without forming a closed loop. We discussed the backtracking algorithm to find Hamiltonian cycles in a graph and provided code implementations in famous languages like Python, Java, and C++, we also learned that the time complexity of the backtracking algorithm is O(n!), and the space complexity is O(n), which makes it inefficient for large graphs.
You can also practice coding questions commonly asked in interviews on Code360.
Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.
518+ registered 
