标签: hamiltonian-path

有人可以告诉我汉密尔顿路径和欧拉路径之间的区别.他们似乎相似!

我最近在考虑一个可能的解决方案，以在多项式时间内找到无向图是否具有哈密顿路径。

作为此实现的一部分使用的主要概念基于我在尝试为几个无向图找到（即在纸上）哈密顿路径时注意到的观察结果。

这些步骤可以定义如下：

1. 读取图的邻接矩阵。

2. 在读取邻接矩阵时，将为所有节点创建一个映射（即基于字典的结构）。此外，在读取邻接矩阵时将选择路径的起始节点。这些操作可以描述如下：
   
   

   2.1. 映射将存储图中的所有节点，作为键-值结构。

   映射中的每个条目将表示为：（键：节点索引，值：节点类）

   节点类将包含有关节点的以下详细信息：节点索引、其关联边的数量以及指示当前节点是否已被访问过的标志。

   考虑到映射中的每个条目将仅包含对应于该节点的值，可以说对于给定节点索引从映射中进行的任何读取访问都将是恒定的（即 O(1)）。
   
   

   2.2. 作为在步骤 2.1. 中读取邻接矩阵和构建地图的一部分，起始节点也将被保留。路径的起始节点将由具有最少边数的节点表示。

   如果图中存在多个具有此属性的节点，则将选择索引号最低的节点。在这种情况下，我们可以假设每个节点都有一个与之关联的索引，从零开始：0、1、2 等。
   
   

3. 在步骤 2.2 中标识的起始节点。将被标记为已访问。

4. 其余节点将进行下一步操作。当访问节点的数量等于图中节点的数量时，或者当没有找到当前节点的未访问相邻节点时，循环将结束。

   因此，接下来的步骤将作为此循环的一部分进行：
   
   

   4.1. 第一个操作是寻找下一个要访问的节点。

   要访问的下一个节点必须遵守以下约束：

   • 拥有到当前节点的边
   • 到目前为止还没有被访问过
   • 与当前节点的其他相邻节点相比，具有最少数量的边缘。
     
     

   4.2. 如果没有找到下一个节点，那么算法将结束并指示没有找到哈密顿路径。
   
   

   4.3. 如果找到了下一个节点，则这将代表当前节点。它将被标记为已访问，并且已访问节点的数量将增加。
   
   

5. 如果访问节点的数量等于图中节点的数量，则已找到哈密顿路径。无论哪种方式，都会根据算法的结果显示一条消息。

GitHub 上提供了实现/测试：https : //github.com/george-cionca/hamiltonian-path

我的主要问题是：

1. 是否有无向图会导致该算法无法生成正确的解决方案？
2. 在存储库的页面上，我包含了更多详细信息，并说明此实现提供了二次时间（即 O(n ² )）的解决方案。有没有我没有考虑到时间复杂度的方面？