哈密顿环
在无向图中，哈密顿路径是一条路径，该路径仅访问每个顶点一次，哈密顿循环或回路是哈密顿路径，即从最后一个顶点到第一个顶点都有一条边。
在此问题中，我们将尝试确定图是否包含哈密顿循环。并且当存在哈密顿循环时，也要打印该循环。
输入输出
Input: The adjacency matrix of a graph G(V, E).Output: The algorithm finds the Hamiltonian path of the given graph. For this case it is (0, 1, 2, 4, 3, 0). This graph has some other Hamiltonian paths. If one graph has no Hamiltonian path, the algorithm should return false.
算法
isValid(v,k)
输入- 顶点v和位置k。
输出-检查将v放置在位置k是否有效。
Begin
if there is no edge between node(k-1) to v, then
return false
if v is already taken, then
return false
return true; //otherwise it is valid
EndcycleFound（节点k）
输入-图的节点。
输出-当存在哈密顿循环时为true，否则为false。
Begin
if all nodes are included, then
if there is an edge between nodes k and 0, then
return true
else
return false;
for all vertex v except starting point, do
if isValid(v, k), then //when v is a valid edge
add v into the path
if cycleFound(k+1) is true, then
return true
otherwise remove v from the path
done
return false
End示例
#include<iostream>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{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},
};
/* int graph[NODE][NODE] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
}; */
int path[NODE];
void displayCycle() {
cout<<"Cycle: ";
for (int i = 0; i < NODE; i++)
cout << path[i] << " ";
cout << path[0] << endl; //print the first vertex again
}
bool isValid(int v, int k) {
if (graph [path[k-1]][v] == 0) //if there is no edge
return false;
for (int i = 0; i < k; i++) //if vertex is already taken, skip that
if (path[i] == v)
return false;
return true;
}
bool cycleFound(int k) {
if (k == NODE) { //when all vertices are in the path
if (graph[path[k-1]][ path[0] ] == 1 )
return true;
else
return false;
}
for (int v = 1; v < NODE; v++) { //for all vertices except starting point
if (isValid(v,k)) { //if possible to add v in the path
path[k] = v;
if (cycleFound (k+1) == true)
return true;
path[k] = -1; //when k vertex will not in the solution
}
}
return false;
}
bool hamiltonianCycle() {
for (int i = 0; i < NODE; i++)
path[i] = -1;
path[0] = 0; //first vertex as 0
if ( cycleFound(1) == false ) {
cout << "Solution does not exist"<<endl;
return false;
}
displayCycle();
return true;
}
int main() {
hamiltonianCycle();
}输出结果
Cycle: 0 1 2 4 3 0