给定一个无向图，你如何确定是否存在一条连接所有节点的路径，以便每个节点只被访问一次？

Question

图可以是循环的或非循环的。目标是确定是否存在从任何节点到另一个节点的路径，其中每个节点都被访问一次。

例如图

A <=> B
B <=> C
B <=> D

没有路径。没有办法构建包含每个节点的路径，其中每个节点只被访问一次。

我们可以假设每条边的长度相同，因为我们只是在寻找路径的存在。我从最初的搜索中找不到任何好的算法，但我可能错过了！

这只是我遇到的一个有趣的问题。让我知道是否需要更多信息！

Answer 1

我的解决方案是遍历图形的每个顶点，然后从那里开始。然后递归地遍历每个相邻节点以查看是否可以从该子路径中找到一条路径。但是我相信这个解决方案是n^2，所以我想知道是否有更好的解决方案。

伪代码：

def check_graph(graph)
{
   foreach (vertex of graph)
   {
      if (is_path_possible(graph, vertex)
        return true;
   }

   return false;
}


def is_path_possible(graph, source) 
{
  if !graph.nodes.contains(source)
    return false;

  if graph.nodes.count == 1
    return true;

  foreach (neighbor of source)
  {
    child_graph = graph - source;

    is_child_path_possible = is_path_possible(child_graph, neighbor);

    if (is_child_path_possible)
      return true;
  }

  return false;
}

Answer 2

这是一个Hamiltonian path problem，没有办法轻易解决。这个问题属于 NP-complete class，一般来说，此类问题需要指数级的时间和内存来解决正好。但是有一些相当复杂的启发式算法。比如"traveling salesman problem"是哈密顿路径问题的一个特例，大家可以看看解法

给定一个无向图，你如何确定是否存在一条连接所有节点的路径，以便每个节点只被访问一次？

Given an undirected graph, how do you determine if there exists a path, that connects all nodes, so each node is only visited once?

graph-theory

theory