C++ 哈密顿环检测

在本文中，我们将讨论 C++ 中的哈密顿回路检测，并提供几个示例。

什么是哈密顿回路？

哈密顿回路或回路 G 是一种在返回第一个顶点之前精确地遍历每个顶点一次的回路。如果一个图具有哈密顿回路，则称其为哈密顿图；否则，它是非哈密顿图。

目前还没有有效的解决方案来解决所有已知图形式的图中寻找哈密顿回路的众所周知的 NP 完全问题。它可以通过解决小型或特殊类型的图来解决。

哈密顿回路问题在计算机科学、网络设计和物流等许多学科中都有实际应用。

哈密顿路径是什么意思？

在图 G 中，哈密顿路径是精确地访问每个顶点一次且不需要返回起始顶点的路径。在一般图中寻找哈密顿路径是 NP 完全问题，可能很困难，就像哈密顿回路问题一样。尽管如此，它通常比定位哈密顿回路的任务更简单。

哈密顿路径的应用包括电路设计、图论研究和确定交通网络中的最佳路径。

回溯

回溯是一种基于递归解决问题的算法方法，它涉及逐步创建每个解决方案，并消除任何未能满足问题限制的解决方案。

让我们回顾一下哈密顿回路的定义。

哈密顿回路

为了从任何源顶点返回起始顶点，我们必须精确地访问每个顶点一次。

现在让我们检查一下这个问题。

问题陈述

让我们以一个有 N 个节点的无向图为例。该图表示为一个维度为 N x N 的邻接矩阵。我们的任务是打印所有可能的哈密顿回路。

示例

这是显示给定图的方式

给定图由邻接矩阵表示。

{ 0, 1, 1, 0, 0, 1 }

{ 1, 0, 1, 0, 1, 1 }

{ 1, 1, 0, 1, 0, 0 }

{ 0, 0, 1, 0, 1, 0 }

{ 0, 1, 0, 1, 0, 1 }

{ 1, 1, 0, 0, 1, 0 }

输出

0 1 2 3 4 5 0

0 1 5 4 3 2 0

0 2 3 4 1 5 0

0 2 3 4 5 1 0

0 5 1 4 3 2 0

0 5 4 3 2 1 0

我们可以看到，通过精确地遍历图中的每个顶点一次，我们可以通过 0->1->2->3->4->5->0 的形式到达我们的源（在这种情况下，为 0）。正如我们的报告所示，我们可以使用多条路径重复相同的过程。

工作机制

下一步是采用以下方法来打印无向图中的每个哈密顿回路。

1. 为了确定当前正在考虑的顶点是否不已经是路径的一部分并且不邻近前面的顶点，我们必须首先构建一个函数。
2. 如果满足前两个条件，则可以安全地计算该顶点。
3. 之后，将定义用于查找所有哈密顿回路的函数。将存在从最后一个顶点到第一个顶点的路径，并且所有图的顶点都将存在。
4. 源顶点将是我们路径的一部分，并且将打印完整路径。打印路径后，必须删除源顶点。
5. 要为即将到来的顶点找到新路径，请重复上述步骤。
6. 我们将打印所有可能的哈密顿回路。如果上述条件不满足，我们将说明没有哈密顿回路是可行的。

打印无向图中所有哈密顿回路的伪代码

过程 isSafe(int v, int graph[][6], vector<int> path, int pos)

过程 FindHamCycle(int graph[][6], int pos, vector<int> path, bool visited[], int N)

过程 hamCycle(int graph[][6], int N)

程序

输出

Hamiltonian Cycle: 0 1 2 3 4 5 0

复杂度评估

时间复杂度：O(N!)。

矩阵执行 N! 次迭代，其中 N 是网络中的节点数。

空间复杂度：O(N).

由于图中存在 N 个节点，因此打印路径所需的空间将占用 N 个节点。