Given an undirected graph, determine whether a Hamiltonian path exists. A Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. If a Hamiltonian path exists, return true; otherwise, return false.

For example, consider the following graph represented by an adjacency list:

{ 0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 4], 3: [1, 4], 4: [2, 3] }

A Hamiltonian path in this graph is [0, 1, 2, 4, 3]. Therefore, your function should return true.

Now consider the following graph:

{ 0: [1, 2], 1: [0, 2], 2: [0, 1] }

It is not possible to visit all vertices exactly once in a path. Therefore, your function should return false.

Your task is to implement a function that takes the number of vertices n and the adjacency list representation of the graph graph as input and returns a boolean value indicating whether a Hamiltonian path exists in the graph. The graph will contain n vertices labeled from 0 to n-1.

Constraints:

1 <= n <= 10
The graph is undirected.
There are no self-loops.
There are no duplicate edges.

Hamiltonian Path

Problem

Naive Approach: Brute-Force

The most straightforward approach is to generate all possible permutations of vertices and check if any of them form a valid path in the graph. This involves trying every possible order of vertices to see if it constitutes a Hamiltonian path.

def is_hamiltonian_path_brute_force(n: int, graph: dict[int, list[int]]) -> bool:
    import itertools

    def is_valid_path(path: list[int], graph: dict[int, list[int]]) -> bool:
        for i in range(len(path) - 1):
            if path[i+1] not in graph.get(path[i], []):
                return False
        return True

    for path in itertools.permutations(range(n)):
        if is_valid_path(list(path), graph):
            return True
    return False

# Example Usage:
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 4],
    3: [1, 4],
    4: [2, 3]
}
n = 5
print(f"Hamiltonian path exists (brute force): {is_hamiltonian_path_brute_force(n, graph)}")

graph2 = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}
n2 = 3
print(f"Hamiltonian path exists (brute force): {is_hamiltonian_path_brute_force(n2, graph2)}")

Time Complexity of Brute-Force Approach

The brute-force approach generates all n! permutations of vertices and, for each permutation, checks if it's a valid path. Verifying each path takes O(n) time. Therefore, the overall time complexity is O(n! * n).

Space Complexity of Brute-Force Approach

The space complexity is dominated by the itertools.permutations function, which needs to store a permutation. Thus the space complexity is O(n).

Optimal Approach: Backtracking

A more efficient approach is to use backtracking to explore possible paths. Backtracking allows us to explore paths one vertex at a time, and if a path doesn't lead to a solution, we can backtrack and try a different path. This avoids generating all possible permutations.

def has_hamiltonian_path(n: int, graph: dict[int, list[int]]) -> bool:
    def solve(start_node: int):
        path = [start_node]
        visited = {start_node}

        def backtrack() -> bool:
            if len(path) == n:
                return True

            for neighbor in graph.get(path[-1], []):
                if neighbor not in visited:
                    path.append(neighbor)
                    visited.add(neighbor)
                    if backtrack():
                        return True
                    path.pop()
                    visited.remove(neighbor)
            return False

        return backtrack()

    # Try starting from each node
    for start_node in range(n):
        if solve(start_node):
            return True
    return False


# Example Usage:
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 4],
    3: [1, 4],
    4: [2, 3]
}
n = 5
print(f"Hamiltonian path exists (backtracking): {has_hamiltonian_path(n, graph)}")

graph2 = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}
n2 = 3
print(f"Hamiltonian path exists (backtracking): {has_hamiltonian_path(n2, graph2)}")

graph3 = {
    0: [1],
    1: [0, 2],
    2: [1,3],
    3: [2]
}
n3 = 4
print(f"Hamiltonian path exists (backtracking): {has_hamiltonian_path(n3, graph3)}")

Time Complexity of Backtracking Approach

The time complexity of the backtracking approach is O(n!), as in the worst-case scenario, it might explore all possible paths. However, in practice, it tends to perform much better than the brute-force approach because it prunes branches of the search tree that cannot lead to a solution.

Space Complexity of Backtracking Approach

The space complexity is O(n) due to the path list and visited set, which store at most n vertices. The recursion stack can also grow up to n in depth in the worst case.

Edge Cases

Empty Graph: If the graph has no vertices (n = 0), then by definition, a Hamiltonian path exists (vacuously true). The provided code will not handle this case. A check for n == 0 at the start would handle it.
Disconnected Graph: If the graph is disconnected, no Hamiltonian path can exist. The algorithm will still run, but it will correctly return false.
Single Vertex: If the graph has only one vertex (n = 1), a Hamiltonian path trivially exists.
Complete Graph: A complete graph (where every vertex is connected to every other vertex) will always have a Hamiltonian path.
Graph with n > 10: According to the constraints, 1 <= n <= 10. With larger graphs, the backtracking approach can still be used, but the execution time will increase dramatically. Heuristics and optimizations might become necessary for very large graphs.

Conclusion

The backtracking approach provides a more efficient way to determine if a Hamiltonian path exists in a given graph compared to the brute-force approach. It avoids exploring unnecessary paths by pruning the search tree whenever a dead-end is encountered. While both approaches have a worst-case time complexity of O(n!), the backtracking approach performs better in practice for most graphs. The algorithm also correctly handles edge cases such as disconnected graphs and graphs with a single vertex.