首页 > 搜索 > 回溯和剪枝 > 哈密顿回路-回溯法
2014
06-11

哈密顿回路-回溯法

哈密顿图(英语:Hamiltonian path,或Traceable path)是一个无向图,由天文学家哈密顿提出,由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图,闭合的哈密顿路径称作哈密顿回路(Hamiltonian cycle),含有图中所有顶的路径称作哈密顿路径。
对一个给定的图确定其是否包含哈密顿回路。如果它包含,那么打印路径。以下是函数所需的输入和输出。
输入:
二维数组 graph[V][V]图的邻接矩阵表示。graph[i][j] = 1 如果有一条从 i 到 j的边, 否则graph[i][j] = 0。
输出:
如果该图包含哈密顿回路,则输出path[V],代表路径。否则返回FALSE。

例如:下面的一个哈密顿回路为 {0, 1, 2, 4, 3, 0},或者 {0, 3, 4, 2, 1, 0}

(0)--(1)--(2)
 |   / \   |
 |  /   \  |
 | /     \ |
(3)-------(4)

下面的图没有哈密顿回路

(0)--(1)--(2)
 |   / \   |
 |  /   \  |
 | /     \ |
(3)      (4)

哈密顿回路和N皇后等问题类似,属于NP难题。一般应用回溯法准确求解。

#include <iostream>
#include <stdio.h>
using namespace std;
const int V = 5;

void printSolution(int path[])
{
    printf ("Solution Exists:"
            " Following is one Hamiltonian Cycle \n");
    for (int i = 0; i < V; i++)
        printf(" %d ", path[i]);

    printf(" %d ", path[0]);
    printf("\n");
}

//path记录路径,visited记录顶点是否访问过,len记录当前路径的长度
bool hamCycleRecall(int graph[V][V], int path[V], bool visited[V],int len){
	if(len == V){ //访问到最后一个顶点
		if( graph[ path[V-1] ][0] == 1) //有到0点的边
			return true;
		else
			return false;
	}
	//遍历其它顶点
	for(int v = 1; v<V; v++){
		//如果没访问过,并且有边相连
		if(!visited[v] && graph[ path[len-1] ][v] ==1){
			visited[v] = true;
			path[len] = v;

			//找到了就直接返回
			if( hamCycleRecall(graph, path, visited, len+1) )
				return true;

			path[len] = -1;
			visited[v] = false;
		}
	}
	return false;
}

//查找从第一个顶点0开始,能否找到一条哈密顿回路。
bool hamCycle(int graph[V][V]){
	int path[V] = {-1};
	bool visited[V] = {0};
	path[0] = 0; 
	visited[V] = true; //第一个顶点标记为访问过

	//第一个顶点已确定,len从1开始
	if( hamCycleRecall(graph, path,visited, 1) == false){
		 printf("\nSolution does not exist");
		 return false;
	}

	printSolution(path);
	return true;
}

//测试
int main() {
/* 创建以下的图
      (0)--(1)--(2)
       |   / \   |
       |  /   \  |
       | /     \ |
      (3)-------(4)    */
	 int graph[V][V] = {{0, 1, 0, 1, 0},
	                      {1, 0, 1, 1, 1},
	                      {0, 1, 0, 0, 1},
	                      {1, 1, 0, 0, 1},
	                      {0, 1, 1, 1, 0},
	                     };

	hamCycle(graph);
	return 0;
}

参考:http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/


  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。