Hamiltonian path
A path in a graph that visits every vertex exactly once. Unlike a Hamiltonian cycle, it does not have to return to its start vertex. Deciding existence is NP-complete in general.
Backtracking DFS
Depth-first search over simple paths: pick a start vertex, extend by an unvisited neighbour, recurse. On dead-end, undo the last step (backtrack) and try the next candidate. Without pruning, runs in worst-case exponential time.
"States" counter
Each entry into the recursive extension routine counts as one state. Equivalent to "DFS nodes explored". The headline metric for comparing vanilla DFS against pruned DFS.
Precheck
A cheap necessary condition computed before search. If a precheck fails, the search is skipped and "no Hamiltonian path" is reported immediately. None of the prechecks here can give a false negative — they only reject graphs that truly have no Hamiltonian path.
Connectivity precheck (undirected)
An undirected graph that isn't connected can't have a Hamiltonian path — a path is itself connected, so it can't span disconnected components.
Degree-1 precheck (undirected)
A Hamiltonian path has at most two endpoints. Any vertex of degree 1 must be one of those endpoints. So a graph with three or more degree-1 vertices can't have a Hamiltonian path.
Cut-vertex blocks precheck (undirected)
A cut vertex (articulation point) that sits in three or more biconnected blocks can't be visited by a Hamiltonian path: the path uses at most two edges at any internal vertex, so it can only weave through at most two of the cut vertex's blocks.
Bridge-tree precheck (undirected)
In the bridge tree (2-edge-connected components as nodes, bridges as edges), every component must have at most two incident bridges. A Hamiltonian path enters and leaves each component at most once.
SCC condensation precheck (directed)
For a directed graph, the condensation DAG of its strongly connected components must itself admit a Hamiltonian path (which is a polynomial check, since it's a DAG). If the condensation doesn't, the original graph cannot.
Reachability prune
At every DFS step, every still-unvisited vertex must be reachable from the current endpoint through unvisited intermediaries. If some unvisited vertex is unreachable, the branch can't be completed — prune it without descending further.
MRV ordering
Minimum-remaining-values heuristic: try candidates in ascending order of their unvisited onward degree. Vertices with few onward options tend to commit or fail early, which generally reduces search.
Longest-path DP on a DAG
DP = dynamic programming. Process vertices in topological order. For each vertex v, set L(v) = 1 + max{L(u) : (u → v) ∈ E} (or 1 if no incoming edge). Remember the argmax as pred(v) for reconstruction. Total time O(|V| + |E|).
Hamiltonian-path test (DAG)
For a DAG, a Hamiltonian path exists iff its longest path has length |V| — the longest path is forced to visit every vertex. Reconstruction follows pred backwards.