问题描述:

（1）哈密顿环问题：输入是一个无向连通图G=(V,E)；如果G中存在哈密顿环则输出该环。

（2）最小哈密顿环问题：输入是一个无向连通图G=(V,E)，每个节点都没有到自身的边，每对节点间都有一条非负加权边；输出一个权值代价和最小的哈密顿环。注意：事实上输入图是一个完全图，因此哈密顿环是一定存在的。

实现哈密顿环搜索算法

（1）哈密顿环问题：(a)实现基于树的基本搜索算法(BFS,DFS) (b)爬山法

（2）最小哈密顿环问题：(a)实现求解最小哈密顿环问题的分支界限算法。

1.DFS

算法的主要步骤:

2.BFS

算法的主要步骤:

3.ClimbingHill

算法的主要步骤:

4.BranchBound

算法的主要原理:

源码：

Grap.h

/*
*Tree Search Strategy 15S103182 Ethan
*2015.12.1
*/
#include<iomanip>
#include<limits>
#include<time.h>
#include<stdlib.h>
#include<iostream>
#include<fstream>
using namespace std;

template<class E>  //E为图中边的权值的数据类型
class Graph {
	private:
		int maxVertices; //图中最大顶点数
		E **matrix;//邻接矩阵

	public:
		E maxWeight; //代表无穷大的值
		Graph(int sz);//创建SZ大小的基于邻接矩阵的图
		~Graph();//析构函数
		int NumberOfVertices() {
			return maxVertices;    //返回最大顶点数
		}
		E getWeight(int v1, int v2);     //取边（v1,v2)上的权值
		int getFirstNeighbor(int v);//取顶点v的第一个邻接顶点
		int getNextNeighbor(int v, int w);//取顶点v的邻接顶点W的下一个邻接顶点

		int Init(istream &in);//根据用户输入，获得图的邻接矩阵
		int RandInitN();//随机初始化图(无向图)
		int RandInit();//随机初始化图(完全无向图)
		int output(ostream &out); //输出图的矩阵到文件
		int output(); //输出图的矩阵到控制台
};

template<class E>
Graph<E>::Graph(int sz) { //创建SZ大小的基于邻接矩阵的图
	maxWeight = std::numeric_limits<E>::max();
	maxVertices = sz;
	matrix = new E *[sz];
	for (int i = 0; i<sz; i++) {
		matrix[i] = new E[sz];
		for (int j = 0; j<sz; j++) {
			matrix[i][j] = maxWeight;
		}
	}
}
template<class E>
Graph<E>::~Graph() {
	for (int i = 0; i<maxVertices; i++) {
		delete matrix[i];
	}
}
template<class E>
E Graph<E>::getWeight(int v1, int v2) { //取边（v1,v2)上的权值
	if (v1 >= 0 && v1<maxVertices&&v2 >= 0 && v2<maxVertices) {
		return matrix[v1][v2];
	}
	return 0;
}
template<class E>
int Graph<E>::getFirstNeighbor(int v) { //取顶点v的第一个邻接顶点
	if (!(v >= 0 && v<maxVertices))   //v不合法
		return -1;
	for (int col = 0; col<maxVertices; col++) {
		if (matrix[v][col] != maxWeight) {
			return col;          //找到
		}
	}
	return -1;                   //未找到
}
template<class E>
int Graph<E>::getNextNeighbor(int v, int w) { //取顶点v的邻接顶点W的下一个邻接顶点
	if (!(v >= 0 && v<maxVertices) || !(w >= 0 && w<maxVertices))  //v或w不合法
		return -1;
	for (int col = w + 1; col<maxVertices; col++) {
		if (matrix[v][col] != maxWeight) {
			return col;         //找到
		}
	}
	return -1;//未找到
}
template<class E>
int Graph<E>::Init(istream &fin) { //根据输入文件，获得图的邻接矩阵
	int v1, v2;
	E edge;
	while (fin >> v1 >> v2 >> edge) {
		if (v1 >= 0 && v1<maxVertices&&v2 >= 0 && v2<maxVertices) {
			matrix[v1][v2] = edge;
			matrix[v2][v1] = edge;
		}
		if (edge == maxWeight) {  //当输入边值为无穷大时停止输入
			break;
		}
	}
	return 1;
}

template<class E>
int Graph<E>::RandInitN() { //随机初始化图(无向图,非完全)
	for (int i = 0; i<maxVertices; i++) {
		for (int j = 0; j<maxVertices; j++) {
			matrix[i][j] = maxWeight;
		}
	}
	srand((int)time(0));
//	int rnd = maxVertices*(maxVertices - 1) / 3;
////	int count = rand() / RAND_MAX*rnd / 4 + 3 * rnd / 4;
//	int count = rnd / 2;
//	int v1, v2;
//	while (count) {
//		v1 = rand() % maxVertices;
//		v2 = rand() % maxVertices;
//		if (v1 != v2&&matrix[v1][v2] == maxWeight) {
//			matrix[v2][v1] = matrix[v1][v2] = rand();
//			count--;
//		}
//	}
	for(int v1=0;v1<maxVertices;v1++)
		for(int v2=0;v2<maxVertices;v2++){
			if (v1 != v2&&matrix[v1][v2] == maxWeight){
				matrix[v2][v1] = matrix[v1][v2] = rand()%2;
			}
		}
	return 1;
}

template<class E>
int Graph<E>::RandInit() { //随机初始化图(无向完全图)
	for (int i = 0; i<maxVertices; i++) {
		for (int j = 0; j<maxVertices; j++) {
			matrix[i][j] = maxWeight;
		}
	}
	srand((int)time(0));
	int count = maxVertices*(maxVertices - 1) / 2;
	int v1, v2;
	while (count) {
		v1 = rand() % maxVertices;
		v2 = rand() % maxVertices;
		if (v1 != v2&&matrix[v1][v2] == maxWeight) {
			if(v1-v2==1||v2-v1==1) matrix[v2][v1] = matrix[v1][v2] = rand()%2000;
			else matrix[v2][v1] = matrix[v1][v2] = rand();
			count--;
		}
	}
	return 1;
}

template<class E>
int Graph<E>::output(ostream &out) { //输出图的矩阵
	for (int i = 0; i<maxVertices; i++) {
		for (int j = 0; j<maxVertices; j++) {
			out << setw(15) << matrix[i][j] << ",";
		}
		out << endl;
	}
	return 1;
}
template<class E>
int Graph<E>::output() { //输出图的矩阵
	for (int i = 0; i<maxVertices; i++) {
		cout<<"	";
		for (int j = 0; j<maxVertices; j++) {
			cout << setw(15) << matrix[i][j] << ",";
		}
		cout << endl;
	}
	return 1;
}

源码：

Graph.cpp

/*
*Tree Search Strategy 15S103182 Ethan
*2015.12.1
*/
#include"Graph.h"
#include<iostream>
#include<fstream>
#include<sstream>
#include<stack>
#include<queue>
#include<limits>
#include<memory.h>
#include<string.h>
using namespace std;

template<class E>
struct NODE {
	int dep;        //表示该结点在搜索树的第几层
	int *vertices;  //该节点包含的各个顶点
	E length;       //从根到当前结点已经走过的路径长度
	NODE(int depth) {
		dep = depth;
		vertices = new int[dep];
	};
	void cpy(int *&des) {
		for (int i = 0; i<dep; i++) {
			des[i] = vertices[i];
		}
	}
	bool find(int v) {
		for (int i = 0; i<dep; i++) {
			if (vertices[i] == v)
				return true;
		}
		return false;
	}
};

template<class E>
int dfs(int start, Graph<E> &myGraph) { //deepFirst 判断图中是否存在哈密顿回路
	stack<int> myStack;
	myStack.push(start);
	int numVertices = myGraph.NumberOfVertices();
	bool *visited = new bool[numVertices];
	memset(visited, false, numVertices);
	int v;
	int w = -1;
	while (!myStack.empty()) { //栈不为空
		v = myStack.top();
		visited[v] = true;
		if (w == -1) {
			w = myGraph.getFirstNeighbor(v);
		} else {
			w = myGraph.getNextNeighbor(v, w);
		}
		for (; w != -1 && visited[w] == true; w = myGraph.getNextNeighbor(v, w)) {}
		if (w == -1) { //未找到可行的下一个顶点,子节点都在栈中
			myStack.pop();  //回溯
			w = v;
			visited[v] = false;
		} else {  //找到可行的下一个顶点
			myStack.push(w);  //放入栈中
			if (myStack.size() == numVertices) { //走过所有的顶点
				if (myGraph.getWeight(start, w) == std::numeric_limits<E>::max()) { //判断最后一个顶点有没有回到起点的边
					myStack.pop();
					visited[w] = false;
				} else { //成功找到回路
					return 1;
				}
			} else {
				w = -1;
			}
		}
	}
	return 0;
}

template<class E>
int ch(int start, Graph<E> &myGraph) { //climbingHill 爬山法判断图中是否存在哈密顿回路
	stack<int> myStack;
	myStack.push(start);
	int numVertices = myGraph.NumberOfVertices();
	bool *visited = new bool[numVertices];
	memset(visited, false, numVertices);
	int v;
	int w = -1;
	while (!myStack.empty()) { //栈不为空
		v = myStack.top();
		visited[v] = true;
		if (w == -1) {
			w = myGraph.getFirstNeighbor(v);
		} else {
			w = myGraph.getNextNeighbor(v, w);
		}
		for (; w != -1 && visited[w] == true; w = myGraph.getNextNeighbor(v, w)) {}

		int greedy = w;//贪心选择子顶点
		for (; w != -1 && visited[w] == false; w = myGraph.getNextNeighbor(v, w)) {
			if(myGraph.getWeight(v, w) < myGraph.getWeight(v, greedy)) {
				greedy = w;
			}
		}
		w = greedy;
		if (w == -1) { //未找到可行的下一个顶点
			myStack.pop();  //回溯
			w = v;
			visited[v] = false;
		} else {  //找到可行的下一个顶点
			myStack.push(w);  //放入栈中

			if (myStack.size() == numVertices) { //走过所有的顶点
				if (myGraph.getWeight(start, w) == std::numeric_limits<E>::max()) { //判断最后一个顶点有没有回到起点的边
					myStack.pop();
					visited[w] = false;
				} else { //成功找到回路
					return 1;
				}
			} else {
				w = -1;
			}
		}
	}
	return 0;
}

template<class E>
int climbingHill(int start, Graph<E> &myGraph, ostream & fout) { //算法解决图的最小哈密顿回路问题  v为回路的起点和终点
	stack<int> myStack;
	myStack.push(start);
	int numVertices = myGraph.NumberOfVertices();
	bool *visited = new bool[numVertices];
	memset(visited, false, numVertices);
	int v;
	int w = -1;
	while (!myStack.empty()) { //栈不为空
		v = myStack.top();
		visited[v] = true;
		if (w == -1) {
			w = myGraph.getFirstNeighbor(v);
		} else {
			w = myGraph.getNextNeighbor(v, w);
		}
		for (; w != -1 && visited[w] == true; w = myGraph.getNextNeighbor(v, w)) {}
		int greedy = w;//贪心选择子顶点
		for (; w != -1 && visited[w] == false; w = myGraph.getNextNeighbor(v, w)) {
			if(myGraph.getWeight(v, w) < myGraph.getWeight(v, greedy)) {
				greedy = w;
			}
		}
		w = greedy;
		if (w == -1) { //未找到可行的下一个顶点
			myStack.pop();  //回溯
			w = v;
			visited[v] = false;
		} else {  //找到可行的下一个顶点
			myStack.push(w);  //放入栈中
			if (myStack.size() == numVertices) { //走过所有的顶点
				if (myGraph.getWeight(start, w) == std::numeric_limits<E>::max()) { //判断最后一个顶点有没有回到起点的边
					myStack.pop();
					visited[w] = false;
				} else { //成功找到回路
					stack<int> temp;
					while (!myStack.empty()) {
						int n = myStack.top();
						temp.push(n);
						myStack.pop();
					}
					fout << "哈密顿回路 : ";
					E distance = 0;
					int n = temp.top();
					myStack.push(n);
					temp.pop();
					int last = n;
					fout << n << "--";
					while (!temp.empty()) {
						n = temp.top();
						myStack.push(n);
						temp.pop();
						distance += myGraph.getWeight(last, n);
						last = n;
						fout << n << "--";
					}
					fout << start << endl;
					distance += myGraph.getWeight(last, start);
					fout << "总长度为:" << distance << endl;
					return distance;
				}
			} else {
				w = -1;
			}
		}
	}
	return std::numeric_limits<E>::max();
}
template<class E>
int bfs(int start, Graph<E> & myGraph) { //broadFirst 判断图中是否存在哈密顿回路
	stack<NODE<E> > myStack;  //队列
	int s = myGraph.getFirstNeighbor(start);
	for (s = myGraph.getNextNeighbor(start, s); s != -1; s = myGraph.getNextNeighbor(start, s)) {
		NODE<E> n(2);
		n.vertices[0] = start;
		n.vertices[1] = s;
		n.length = myGraph.getWeight(start, s);
		myStack.push(n);
	}
	while (!myStack.empty()) { //队列不为空
		NODE<E> n = myStack.top();
		myStack.pop();
		int v = n.vertices[n.dep - 1];
		if (n.dep + 1 == myGraph.NumberOfVertices()) { //到了最后一层 判断是不是哈密顿回路
			int w;
			for (w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
				if (n.find(w) == false)
					break;
			}
			if (w != -1) {
				if (myGraph.getWeight(w, start)<std::numeric_limits<E>::max()) {
					return 1;
				}
			}
		}
		for (int w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
			if (n.find(w) == false) {
				NODE<E> ne(n.dep + 1);
				ne.length = n.length + myGraph.getWeight(v, w);
				n.cpy(ne.vertices);
				ne.vertices[ne.dep - 1] = w;
				myStack.push(ne);
			}
		}
	}
	return 0;
}
//分支限界法求解最短哈密顿回路问题
template<class E>
int branchBound(int start, Graph<E> & myGraph, ostream & fout) {
	stack<NODE<E> > myStack;  //队列
	E minDistance = climbingHill(start,myGraph,fout);//爬山法获取首界限
	int s = start;
	for (s = myGraph.getFirstNeighbor(start); s != -1; s = myGraph.getNextNeighbor(start, s)) {//首次分支
		NODE<E> n(2);
		n.vertices[0] = start;
		n.vertices[1] = s;
		n.length = myGraph.getWeight(start, s);
		myStack.push(n);
	}
	while (!myStack.empty()) { //队列不为空
		NODE<E> n = myStack.top();
		myStack.pop();
		int v = n.vertices[n.dep - 1];
		if (n.dep + 1 == myGraph.NumberOfVertices()) { //到了最后一层 判断是不是哈密顿回路
			int w;
			for (w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
				if (n.find(w) == false)//确定最后一个节点
					break;
			}
			if (w != -1) {
				if (myGraph.getWeight(w, start)<std::numeric_limits<E>::max()) { //如果找到且存在路径
					E tempDistance = n.length + myGraph.getWeight(v, w) + myGraph.getWeight(w, start);

					if (minDistance>tempDistance) {
//						形成回路
						fout << "哈密顿回路为:";
//						cout << "哈密顿回路为:";
						for (int i = 0; i<n.dep; i++) {
							fout << n.vertices[i] << "   ";
//							cout << n.vertices[i] << "   ";
						}
						fout << w << "   " << start << endl;
//						cout << w << "   " << start << endl;
						fout << "总长度为:  " << tempDistance << endl;
//						cout << "总长度为:  " << tempDistance << endl;
						minDistance = tempDistance;
					}
				}
			}
		}
		for (int w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
			if (n.find(w) == false) {//存在未遍历顶点
				NODE<E> ne(n.dep + 1);
				ne.length = n.length + myGraph.getWeight(v, w);
				if (ne.length<minDistance) {//剪枝
					n.cpy(ne.vertices);
					ne.vertices[ne.dep - 1] = w;
					myStack.push(ne);
				}
			}
		}
	}
	return minDistance;
}

int main(int argc, char** argv) {
	for(int i=8; i<=20; i+=2) {
		cout<<endl<<"节点数:"<<i<<endl;
		Graph<int> myGraph(i);
		Graph<int> myGraphN(i);
		myGraph.RandInit();//随机初始化完全无向图
		myGraphN.RandInitN();//随机初始化图
		int a = clock();
		cout<<"deepFirst:"<<dfs(0,myGraphN)<<"		";
		int b = clock();
		int st = b - a;
		cout<<"dfs time:"<<st<<endl;
		int a1 = clock();
		cout<<"broadFirst:"<<bfs(0,myGraphN)<<"		";
		int b1 = clock();
		int st1 = b1 - a1;
		cout<<"bfs time:"<<st1<<endl;
		int a2 = clock();
		cout<<"climbingHill:"<<ch(0,myGraphN)<<"		";
		int b2 = clock();
		int st2 = b2 - a2;
		cout<<"ch time:"<<st2<<endl;
		char mat[20];
		itoa(i,mat,10);
		strcat(mat,"matrix.txt");
		ofstream fout2(mat);
		myGraph.output(fout2);
		char matN[20];
		itoa(i,matN,10);
		strcat(matN,"matrixN.txt");
		ofstream fout3(matN);
		myGraphN.output(fout3);
//		cout<<"Matrix["<<i<<"]["<<i<<"]:"<<endl;
//		myGraph.output();
		char bbn[20];
		itoa(i,bbn,10);
		strcat(bbn,"branchBound.txt");
		ofstream fout1(bbn);
		
		int a3 = clock();
		cout<<"branchBound:"<<branchBound(0,myGraph,fout1)<<"	";
		int b3 = clock();
		int st3 = b3 - a3;
		cout<<"branchBound time:"<<st3<<endl;
	}
	//手动输入图
//	Graph<int> myGraphN(4);
//	ifstream fin("input.txt");
//	myGraphN.Init(fin);
//	cout<<"deepFirst:"<<dfs(0,myGraphN)<<endl;
//	cout<<"broadFirst:"<<bfs(0,myGraphN)<<endl;
//	cout<<"climbingHill:"<<ch(0,myGraphN)<<endl;
//	ofstream fout2("matrix.txt");
//	myGraphN.output(fout2);
//	cout<<"Matrix[4][4]:"<<endl;
//	myGraphN.output();
//	ofstream fout1("branchBound.txt");
//	cout<<"branchBound:"<<branchBound(0,myGraphN,fout1)<<endl;
	return 0;
}

BranchBound的性能曲线如下图：

由性能曲线图可以看出，当输入完全图的点数增加时，算法的运行时间也会成倍增加，造成这种效果的原因主要是为了求解最优解，算法在最坏情况下复杂度是O(n!)，虽然通过剪枝策略能够大大提高效率，但算法时间复杂度依旧很高。