我最近在考虑一种可能的解决方案，可以在多项式时间内找到无向图是否具有哈密顿路径。
作为这个实现的一部分使用的主要概念是基于我在试图找到（即在纸上）几个无向图的哈密顿路径时注意到的观察。
这些步骤可以定义如下：
读取图的邻接矩阵。
在读取邻接矩阵时，将为所有节点创建一个映射（即基于字典的结构）。此外，在读取邻接矩阵时，将选择路径的起始节点。这些操作可以描述如下：
2.1。map 将存储图中的所有节点，作为键值结构。
映射中的每个条目将表示为：（键：节点索引，值：节点类）
节点类将包含有关节点的以下详细信息：节点索引、它的事件边数以及指示当前节点是否已被访问的标志。
考虑到映射中的每个条目将只包含与该节点对应的值，可以说从映射中对给定节点索引的任何读取访问都是恒定的（即 O(1)）。
2.2. 作为在步骤 2.1 读取邻接矩阵和构建地图的一部分，起始节点也将被保留。路径的起始节点将由与其关联的边数最少的节点表示。
如果图中存在多个具有此属性的节点，则将选择具有最低索引号的节点。在这种情况下，我们可以假设每个节点都有一个与之关联的索引，从零开始：0、1、2 等。
在步骤 2.2 中确定的起始节点。将被标记为已访问。
其余节点将遵循下一个操作。当访问节点的数量等于图中的节点数量时，或者当没有找到当前节点的未访问的相邻节点时，循环将结束。
因此，接下来的步骤将作为此循环的一部分进行：
4.1。第一个操作是寻找下一个要访问的节点。
下一个要访问的节点必须遵守以下约束：
- 拥有当前节点的边
- 到目前为止还没有访问过
- 与当前节点的其他相邻节点相比，具有最少数量的边缘。
4.2. 如果未找到下一个节点，则算法将结束并指示未找到哈密顿路径。
4.3. 如果找到下一个节点，则这将代表当前节点。它将被标记为已访问，并且访问节点的数量将增加。
如果访问节点的数量等于图中的节点数量，则已找到哈密顿路径。无论哪种方式，都会根据算法的结果显示一条消息。
GitHub 上提供了实现/测试：https ://github.com/george-cionca/hamiltonian-path
我的主要问题是：
- 是否有无向图会导致该算法无法生成正确的解决方案？
- 在存储库的页面上，我包含了更多细节，并指出此实现提供了二次时间的解决方案（即 O(n 2 )）。有没有我没有考虑到时间复杂度的任何方面？