设G=(V,E)是一个n结点的连通图。一个哈密顿环是一条沿着图G的n条边环行的路径，它访问每个结点一次并且返回到它的开始位置。换言之，如果一个哈密顿环在某个结点v1∈V处开始，且G中结点按照v1,v2,…,Vn+l的次序被访问，则边(Vi,Vi+1)，1≤i≤n，均在图G中，且除了v1和vn+l是同一个结点外，其余的结点均各不相同。
用向量(x1, …, xn)表示用回溯法求得的解，其中xi是找到的环中第i个被访问的结点。如果已选定x1, …, xk-1，那么下一步要做的工作是如何找出可能作Xk的结点集合。若k=l，则X(1)可以是这n个结点中的任一结点，但为了避免将同一个环重复打印n次，可事先指定X(l)=1。若1＜k＜n，则X(k)可以是不同于X(1),X(2), …, X(k-1)且和X(k-1)有边相连的任一结点v。X(n)只能是唯一剩下的且必须与X(n-1)和X(1)皆有边相连的结点。
过程NextValue给出了在求哈密顿环的过程中如何找下一个结点的算法。
生成下一个结点,代码如下：
void NextValue(int k) { //X(l),…,X(k-1)是一条有k-l个不同结点的路径。若X(k)=0，则表示再无结 //点可分配给X(k)。若还有与X(1),…,X(k-1)不同且与X(k-1)有边相连结的 //结点则将其中标数最高的结点置于X(k)。若k=n，则还需与X(1)相连结。 int n，X[n]；bool Graph[n][n]； // n、X[n]定义成全局变量 int k，j； while(1) { X[k]=(x[k] + 1) mod (m+1) //下一个结点 if(X[k]==0) { return；} if(Graph[X[k-1]],X[k]) { //有边相连吗 for(j=1；j<=k-1；++j) { //检查与前k-1个结点是否相同 if(X[j]==X[k]) break； //有相同结点，出此循环 }；//for if(j==k) { //若为真，则是一个不同结点 if((k<n) or (k==n and Graph[X[n]],[1] ) return； }；//if }；//if }//while }//NextValue
使用过程NextValue和将递归回溯算法细化得到算法Hamiltonian。此算法可找出所有的哈密顿环。
找所有的哈密顿环，代码如下：
void Hamiltonian(int k) { //这是找出图G中所有哈密顿环的递归算法。图G用它的布尔邻接矩阵 //Graph(1..n,1..n)表示。每个环都从结点 1开始。 int X[n]； //X[n]定义成全局变量 int k，n； while(1) { //生成X(k)的值 NextValue(k)； //下一个合法结点分配给X(k) if(x[k]==0) return； if(k=＝) { print(X,’1’)；} //打印一个环 else { Hamiltonian(k+1)} //if }//repeat }//Hamiltonian
这个过程首先初始化邻接矩阵Graph(l..n,l..n)，然后置X(2:n)=0，X(l)=l，再执行Hamiltonian(2)
