图论哈密尔顿圈算法程序

哈密尔顿圈问题是图论中的经典问题，它要求找到一条遍历图中每个顶点一次且仅一次的闭合路径。要解决哈密尔顿圈问题，可以使用回溯法或动态规划等算法。下面是一个简单的哈密尔顿圈算法程序示例：

def hamiltonian_cycle(graph, start_vertex, path=[]):
    # 检查是否已经遍历完所有顶点
    if len(path) == len(graph) and start_vertex in graph[path[-1]]:
        path.append(start_vertex)
        return path
    
    # 回溯法递归尝试每个未访问过的顶点
    for vertex in graph[start_vertex]:
        if vertex not in path:
            result = hamiltonian_cycle(graph, vertex, path + [start_vertex])
            if result is not None:
                return result
    
    return None

# 测试示例
# 定义一个有向图的邻接表表示
graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['A', 'B', 'C']
}

start_vertex = 'A'
path = hamiltonian_cycle(graph, start_vertex)
if path is not None:
    print("存在哈密尔顿圈：", "->".join(path))
else:
    print("不存在哈密尔顿圈")

在上述示例中，我们使用邻接表来表示有向图。`hamiltonian_cycle` 函数通过回溯法递归地尝试每一个未访问过的顶点，直到找到哈密尔顿圈或所有顶点都遍历完。如果存在哈密尔顿圈，函数将返回一个包含路径的列表；否则，返回 `None`。

请注意，这只是一个简单的示例程序，实际应用中可能需要考虑更多的优化和特殊情况处理。