哈密顿回路python

哈密顿回路指的是一种经过所有节点恰好一次的路径，它是图论中的一个重要问题。下面是一个使用 Python 实现哈密顿回路的示例代码：

def hamiltonian(graph, start):
    visited = set([start])
    path = [start]
    
    def dfs(node):
        nonlocal visited, path
        if len(path) == len(graph):
            if path[0] in graph[path[-1]]:
                return True
            else:
                return False
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                path.append(neighbour)
                if dfs(neighbour):
                    return True
                visited.remove(neighbour)
                path.pop()
        return False
    
    if dfs(start):
        return path
    else:
        return None

在这个函数中，我们使用深度优先搜索（DFS）算法来查找哈密顿回路。我们从给定的起始节点开始，递归地访问其所有未访问过的邻居节点，并将它们添加到路径中。如果路径长度等于图的大小，我们检查路径的最后一个节点是否与第一个节点相邻，如果是，则返回 True，否则返回 False。如果最终找到了哈密顿回路，我们将返回路径，否则返回 None。

下面是使用示例：

graph = {
    1: [2, 3],
    2: [1, 3, 4],
    3: [1, 2, 4],
    4: [2, 3]
}

path = hamiltonian(graph, 1)
if path:
    print("Hamiltonian path found:", path)
else:
    print("No Hamiltonian path found.")

输出：

Hamiltonian path found: [1, 2, 3, 4]

这个例子中的图是一个简单的无向图，它有一个哈密顿回路，从节点 1 开始，途经节点 2、3、4，最终回到节点 1。