Hamiltonian Path Check

Determine if an undirected graph has a Hamiltonian path using DFS and backtracking.

graph dfs backtracking path undirected

Write a function `has_hamiltonian_path(n, edges)` that takes the number of vertices `n` (vertices numbered 0 to n-1) and a list of undirected edges (each edge is a tuple (u, v) with 0 ≤ u, v < n). The function should return `True` if there exists a simple path that visits every vertex exactly once (a Hamiltonian path), and `False` otherwise. A graph with 0 or 1 vertices always has a Hamiltonian path.

Your implementation must use DFS and backtracking. The graph may be disconnected, and edges are undirected. The order of vertices in the path does not matter; just existence.

Constraints

0 ≤ n ≤ 10
0 ≤ len(edges) ≤ n*(n-1)//2
Edges are unique and undirected.
Expected time complexity: O(n!) worst-case, but the small n makes backtracking feasible.

Example

>>> has_hamiltonian_path(4, [(0,1),(1,2),(2,3)])
True
>>> has_hamiltonian_path(4, [(0,1),(2,3)])
False
>>> has_hamiltonian_path(1, [])
True

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Build an adjacency list from the edge list.

Try starting a DFS from every vertex and keep track of visited vertices.

Backtrack: after exploring from a vertex, mark it unvisited to allow other paths.

If all vertices are visited in a path, it's Hamiltonian.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.