哈密顿回路问题回溯法python

哈密顿回路问题是指在一个无向图中找到一条经过每个顶点恰好一次并且回到起点的路径。回溯算法是一种递归算法，常用于解决这类组合优化问题。在Python中，你可以用深度优先搜索（DFS）结合回溯的思想来尝试构建这样的路径。

以下是一个简单的Python代码示例，使用回溯法来寻找哈密顿回路：

def isHamiltonian(path, graph, n):
    if len(path) == n and path[0] == path[-1]:  # 到达终点且首尾相连
        return True
    if len(path) == n:  # 如果已遍历所有节点但未形成环，返回False
        return False

    for i in range(1, n):  # 考虑当前节点之后的所有节点
        if graph.has_path(path, i):  # 检查是否可以添加下一个节点
            path.append(i)
            if isHamiltonian(path, graph, n):  # 递归尝试其他节点
                return True
            path.pop()  # 回溯，尝试下一个节点

    return False


# 示例图的邻接矩阵或邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': ['A']
}

n = len(graph)
path = [0]  # 初始化路径，从第一个节点开始
print("是否存在哈密顿回路:", isHamiltonian(path, graph, n))