哈密顿环
什么是哈密顿环？
哈密顿环或电路是指图中一条路径，它恰好访问每个顶点一次，然后返回起始顶点，形成一个闭环。只有当一个图包含哈密顿环时，才称其为哈密顿图，否则，则称为非哈密顿图。
图是一种抽象数据类型 (ADT)，由一组通过链接连接的对象组成。
哈密顿环问题的实际应用可以在网络设计、配送系统等领域看到。然而，这个问题的解只能在小型图中找到，大型图则无法找到。
输入输出场景
假设给定的无向图 G(V, E) 及其邻接矩阵如下 −
回溯算法可用于在上图中查找哈密尔顿路径。如果找到，算法返回该路径。如果没有找到，则返回 false。在这种情况下，输出应为 (0, 1, 2, 4, 3, 0)。
使用回溯方法查找哈密尔顿环
解决哈密尔顿环问题的简单方法是生成所有可能的顶点配置，并检查是否有任何配置满足给定的约束。然而，这种方法不适用于大型图，因为其时间复杂度为 (O(N!))。
以下步骤解释了回溯法 − 的工作原理。
首先，创建一个空的路径数组，并将起始顶点 0 添加到其中。
接下来，从顶点 1 开始，然后逐个添加其他顶点。
添加顶点时，检查给定顶点是否与先前添加的顶点相邻，并且尚未添加。
如果找到这样的顶点，则将其作为解的一部分添加到路径中，否则返回 false。
示例
以下示例演示如何在给定的无向图中查找哈密顿环。
#include <stdio.h>
#define NODE 5
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 path[NODE];
// 显示哈密顿循环的函数
void displayCycle() {
printf("Cycle Found: ");
for (int i = 0; i < NODE; i++)
printf("%d ", path[i]);
// 再次打印第一个顶点
printf("%d
", path[0]);
}
// 检查将顶点 v 添加到路径是否有效的函数
int isValid(int v, int k) {
// 如果 path[k-1] 和 v 之间没有边
if (graph[path[k - 1]][v] == 0)
return 0;
// 检查顶点 v 是否已在路径中被使用
for (int i = 0; i < k; i++)
if (path[i] == v)
return 0;
return 1;
}
// 查找哈密顿环的函数
int cycleFound(int k) {
// 当所有顶点都在路径上时
if (k == NODE) {
// 检查最后一个顶点和第一个顶点之间是否有边
if (graph[path[k - 1]][path[0]] == 1)
return 1;
else
return 0;
}
// 尝试将每个顶点（起点除外）添加到路径
for (int v = 1; v < NODE; v++) {
if (isValid(v, k)) {
path[k] = v;
if (cycleFound(k + 1) == 1)
return 1;
// 回溯：从路径中移除 v
path[k] = -1;
}
}
return 0;
}
// 查找并显示汉密尔顿循环的函数
int hamiltonianCycle() {
for (int i = 0; i < NODE; i++)
path[i] = -1;
// 将第一个顶点设置为 0
path[0] = 0;
if (cycleFound(1) == 0) {
printf("Solution does not exist
");
return 0;
}
displayCycle();
return 1;
}
int main() {
hamiltonianCycle();
return 0;
}
#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 path[NODE];
// 显示哈密顿循环的函数
void displayCycle() {
cout << "Cycle Found: ";
for (int i = 0; i < NODE; i++)
cout << path[i] << " ";
// 再次打印第一个顶点
cout << path[0] << endl;
}
// 检查将顶点 v 添加到路径是否有效的函数
bool isValid(int v, int k) {
// 如果 path[k-1] 和 v 之间没有边
if (graph[path[k - 1]][v] == 0)
return false;
// 检查顶点 v 是否已在路径中被使用
for (int i = 0; i < k; i++)
if (path[i] == v)
return false;
return true;
}
// 查找哈密顿环的函数
bool cycleFound(int k) {
// 当所有顶点都在路径上时
if (k == NODE) {
// 检查最后一个顶点和第一个顶点之间是否有边
if (graph[path[k - 1]][path[0]] == 1)
return true;
else
return false;
}
// 将每个顶点添加到路径
for (int v = 1; v < NODE; v++) {
if (isValid(v, k)) {
path[k] = v;
if (cycleFound(k + 1) == true)
return true;
// 从路径中删除 v
path[k] = -1;
}
}
return false;
}
// 查找并显示汉密尔顿循环的函数
bool hamiltonianCycle() {
for (int i = 0; i < NODE; i++)
path[i] = -1;
// 将第一个顶点设置为 0
path[0] = 0;
if (cycleFound(1) == false) {
cout << "Solution does not exist" << endl;
return false;
}
displayCycle();
return true;
}
int main() {
hamiltonianCycle();
}
public class HamiltonianCycle {
static final int NODE = 5;
static int[][] graph = {
{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}
};
static int[] path = new int[NODE];
// 显示哈密顿循环的方法
static void displayCycle() {
System.out.print("Cycle Found: ");
for (int i = 0; i < NODE; i++)
System.out.print(path[i] + " ");
// 再次打印第一个顶点
System.out.println(path[0]);
}
// 检查将顶点 v 添加到路径是否有效的方法
static boolean isValid(int v, int k) {
// 如果 path[k-1] 和 v 之间没有边
if (graph[path[k - 1]][v] == 0)
return false;
// 检查顶点 v 是否已在路径中被使用
for (int i = 0; i < k; i++)
if (path[i] == v)
return false;
return true;
}
// 查找汉密尔顿回路的方法
static boolean cycleFound(int k) {
// 当所有顶点都在路径上时
if (k == NODE) {
// 检查最后一个顶点和第一个顶点之间是否有边
if (graph[path[k - 1]][path[0]] == 1)
return true;
else
return false;
}
// 将每个顶点（起点除外）添加到路径
for (int v = 1; v < NODE; v++) {
if (isValid(v, k)) {
path[k] = v;
if (cycleFound(k + 1))
return true;
// 从路径中删除 v
path[k] = -1;
}
}
return false;
}
// 查找并显示汉密尔顿循环的方法
static boolean hamiltonianCycle() {
for (int i = 0; i < NODE; i++)
path[i] = -1;
// 将第一个顶点设置为 0
path[0] = 0;
if (!cycleFound(1)) {
System.out.println("Solution does not exist");
return false;
}
displayCycle();
return true;
}
public static void main(String[] args) {
hamiltonianCycle();
}
}
NODE = 5
graph = [
[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]
]
path = [None] * NODE
# 显示哈密顿循环的函数
def displayCycle():
print("Cycle Found:", end=" ")
for i in range(NODE):
print(path[i], end=" ")
# 再次打印第一个顶点
print(path[0])
# 检查将顶点 v 添加到路径是否有效的函数
def isValid(v, k):
# 如果 path[k-1] 和 v 之间没有边
if graph[path[k - 1]][v] == 0:
return False
# 检查顶点 v 是否已在路径中
for i in range(k):
if path[i] == v:
return False
return True
# 查找哈密顿环的函数
def cycleFound(k):
# 当所有顶点都在路径上时
if k == NODE:
# 检查最后一个顶点和第一个顶点之间是否有边
if graph[path[k - 1]][path[0]] == 1:
return True
else:
return False
# 将每个顶点（起点除外）添加到路径
for v in range(1, NODE):
if isValid(v, k):
path[k] = v
if cycleFound(k + 1):
return True
# 从路径中删除 v
path[k] = None
return False
# 查找并显示汉密尔顿循环的函数
def hamiltonianCycle():
for i in range(NODE):
path[i] = None
# 将第一个顶点设置为 0
path[0] = 0
if not cycleFound(1):
print("Solution does not exist")
return False
displayCycle()
return True
if __name__ == "__main__":
hamiltonianCycle()
输出
Cycle Found: 0 1 2 4 3 0
