以下是一个用于找到图中哈密顿路径的Python函数示例:
def hamiltonian_path(graph, start):
# 创建一个空列表来存储路径
path = [start]
# 获取图中的节点数量
num_nodes = len(graph)
# 创建一个列表来跟踪访问过的节点
visited = [False] * num_nodes
# 将起始节点标记为已访问
visited[start] = True
# 递归寻找哈密顿路径
if find_hamiltonian_path(graph, start, visited, path, num_nodes):
return path
# 如果没有找到哈密顿路径,则返回空列表
return []
def find_hamiltonian_path(graph, curr_node, visited, path, num_nodes):
# 如果路径中的节点数量等于图中的节点数量,则找到哈密顿路径
if len(path) == num_nodes:
return True
# 遍历当前节点的邻居节点
for neighbor in graph[curr_node]:
# 如果邻居节点未访问过,则将其加入路径中,并标记为已访问
if not visited[neighbor]:
path.append(neighbor)
visited[neighbor] = True
# 递归寻找下一个节点
if find_hamiltonian_path(graph, neighbor, visited, path, num_nodes):
return True
# 如果没有找到哈密顿路径,则将当前节点从路径中移除,并标记为未访问
path.pop()
visited[neighbor] = False
# 如果遍历完所有邻居节点仍未找到哈密顿路径,则返回False
return False
请注意,此函数假设图以邻接列表的形式表示,其中graph
是一个列表,其中索引表示节点,列表值表示与该节点相邻的节点列表。start
参数表示起始节点的索引。
使用此函数,您可以找到图中的哈密顿路径。如果找到路径,则该函数返回一个包含路径节点的列表;否则,返回空列表。