1. 说明

• 1.一个无向连通图G点上的哈密尔顿（Hamiltion）回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。

2. c代码实例

#include <stdio.h>
#include <stdlib.h>
#define MAX 4void hamiltion(int n, int x[MAX], int c[MAX][MAX]){int i;int visited[MAX];int k;// 初始化xs数组和visited数组for(i = 0; i<n; i++){x[i] = 0;visited[i] = 0;}// 访问起始顶点k = 0;visited[0] = 1;x[0] = 0;k = k + 1;// 访问其他顶点while(k >= 0){x[k] = x[k] + 1;while(x[k]<n){if(visited[x[k]] == 0 && c[x[k-1]][x[k]] == 1){// 找下一个邻接顶点且x[k]未被访问过，找到后break再做处理break;}else{x[k] = x[k] + 1;}}if(x[k] < n && k == n - 1 && c[x[k]][x[0]] == 1){// 找到一条哈密尔顿回路for(k = 0; k<n; k++){printf("%d--", x[k]);}printf("%d\n", x[0]);return;}else if(x[k] && k < n - 1){// 设置当前顶点的访问标志，继续下一个顶点visited[x[k]] = 1;k = k + 1;}else{// 没有被访问过的邻接顶点，回退到上一个顶点x[k] = 0;visited[x[k]] = 0;k = k - 1;}}
}int main(int argc, char const *argv[]){// n为顶点数量int n = 4;int c[4][4] = {{0,1,0,1},{1,0,1,0},{0,1,0,1},{1,0,1,0}};int x[4] = {0,1,2,3};hamiltion(4, x, c);return 0;
}

3. 邻接矩阵截图

4. 结果截图