1

我目前在业余时间从事一个项目，我需要检查图中是否存在哈密顿路径，但是，路径开始或结束的位置无关紧要，只有一个存在于图中。

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

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 多个顶点的图上运行它，因此需要很长时间才能完成。我真的不需要知道通过所有顶点的路径是什么，我只需要知道存在一个是否有帮助。

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

4

1 回答 1

0

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

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

于 2021-01-26T12:06:45.747 回答