Python 中具有任意起始位置的哈密顿路径

Question

我目前正在业余时间做一个项目，我需要检查图中是否存在哈密顿路径，但是，路径的起点或终点并不重要，只有那个存在于图中。

我从这里的另一个用户那里复制了这段代码：

def hamilton(graph, start_v):
  size = len(graph)
  to_visit = [None, start_v]
  path = []
  while(to_visit):
    v = to_visit.pop()
    if v : 
      path.append(v)
      if len(path) == size:
        break
      for x in set(graph[v])-set(path):
        to_visit.append(None)
        to_visit.append(x)
    else:
      path.pop()
  return path

显然有一个起始值的参数。现在我的第一直觉是只迭代函数并运行它为每个起始顶点，但由于我将运行在具有 100 多个顶点的图上使用它，因此需要很长时间才能运行完成。我真的不需要知道通过所有顶点的路径是什么，我只需要知道是否存在一个路径（如果有帮助的话）。

我如何调整它以提供任意起始位置？

Answer 1

您可以在图中插入一个新的“开始”顶点，边到每个其他顶点，然后搜索从这个“开始”顶点开始的哈密顿路径。如果找到一条路径，则只需从路径的开头删除“开始”顶点即可在原始图中存在该路径；反之，如果原图中有一条从任意顶点开始的哈密顿路径，那么新图中也会有一条从“起始”顶点开始的哈密顿路径。

也就是说，这实际上并不比为每个起始顶点调用一次现有算法更有效，因为您拥有的算法无论如何都是靠蛮力工作的。

Python 中具有任意起始位置的哈密顿路径

Hamiltonian Paths in Python with Arbitrary Starting Positions

python

hamiltonian-path