Course4all
Join us on telegram
Home/dsa/Backtracking/Hamiltonian Path

Hamiltonian Path

Master this topic with zero to advance depth.

Hamiltonian Path

Visiting All Vertices

A Hamiltonian Path is a path in an undirected or directed graph that visits every vertex exactly once.

The NP-Complete Challenge

This is a classic NP-complete problem. Unlike Eulerian paths (which visit every edge), there is no simple polynomial-time check for Hamiltonian paths.

Determine if a graph contains a path that visits every node exactly once. Includes visual node-visit trace.

Hard

Examples

Input: n=4, edges=[[0,1],[1,2],[2,3],[3,0]]
Output: true
Approach 1

Level I: Backtracking with Visited Set

Intuition

Pick a starting node and try to build a path of length N.

Try every node as a starting vertex. Perform DFS, keeping track of visited nodes. If the path length reaches NN, we found a Hamiltonian Path.

⏱ O(N!)💾 O(N)

Detailed Dry Run

N=3. Edges: 0-1, 1-2 1. Start at 0: Visit 0. Next: 1. Visit 1. Next: 2. Visit 2. Length=3. DONE!
java
class HamiltonianPath {
    public boolean hasPath(int n, int[][] adj) {
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (backtrack(i, 1, n, adj, visited)) return true;
        }
        return false;
    }
    private boolean backtrack(int u, int count, int n, int[][] adj, boolean[] visited) {
        if (count == n) return true;
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                if (backtrack(v, count + 1, n, adj, visited)) return true;
            }
        }
        visited[u] = false;
        return false;
    }
}
← Previous QuestionUnique Paths III
Next Question →Course Schedule