問題描述: （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<<"\t"; 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)<<"\t\t"; int b = clock(); int st = b - a; cout<<"dfs time:"<<st<<endl; int a1 = clock(); cout<<"broadFirst:"<<bfs(0,myGraphN)<<"\t\t"; int b1 = clock(); int st1 = b1 - a1; cout<<"bfs time:"<<st1<<endl; int a2 = clock(); cout<<"climbingHill:"<<ch(0,myGraphN)<<"\t\t"; 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)<<"\t"; 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!)，雖然通過剪枝策略能夠大大提高效率，但算法時間復雜度依舊很高。