Python 中的 Hierholzer 算法

引言

在本教程中，我们将学习 Python 中的 Hierholzer 算法。Hierholzer 算法的基本步骤是将不同的圆组合成一个欧拉圆。它从一个随机节点开始。然后，它沿着未访问的边随机地移动到邻居。重复这些步骤直到回到起始节点。第一个圆形成了图。

在图论中，欧拉路径是恰好访问图的所有边一次的路径。具有相同起始点和终点的欧拉路径是欧拉圆，称为欧拉图。我们将使用堆栈和递归来搜索欧拉图中的路径。在这里，我们给出了欧拉图并打印了欧拉回路。欧拉回路是一条经过图中每条边并以起始顶点结束的路径。示例如下 -

示例

我们讨论了确定特定图是否代表欧拉图的问题。本教程讨论了打印欧拉轨道或回路的算法。Fleury 算法也可以解决相同的问题。但是，Fleury 算法的复杂度大于 Hierholzer 算法。Fleury 算法的时间复杂度为 O(E*E)。使用 Hierholzer 算法，我们可以以 O(E) 的时间复杂度找到回路或路径，例如线性时间。算法如下：参考（维基百科）。

请注意，一个图具有欧拉回路的条件是 (1) 所有非零度顶点属于一个连通系统。(2) 每个顶点的内度和外度都相同。此算法假设给定的图有一个欧拉回路。

1. 我们需要选择一个起始顶点 v。然后从该顶点开始，沿着边前进，直到返回 v。不可能停在 v 以外的某个顶点。这是因为当轨道进入另一个顶点时，每个顶点的内度和外度必须是相同的。顶点 w 必须有一条未使用的边 w。这样创建的遍历是一个闭合遍历。但它不覆盖初始图的顶点和边。
2. 当存在一个顶点 u，它属于当前遍历但其邻接边不属于该遍历时，从 u 开始另一条路径。它会使用边，直到返回 u，然后通过这种方式将当前遍历连接到之前的遍历。

因此，目标是跟踪未使用的边并删除它们，直到它们卡住。一旦我们卡住了，我们就返回到当前路径上具有未使用边的最近点，并重复该过程，直到所有边都被使用。我们可以使用另一个容器来保存最后和最终的路径。

程序代码

现在，我们给出了 Hierholzer 算法的程序代码。在这里，我们在 Python 中使用 Hierholzer 算法来打印给定有向图的欧拉回路。代码如下 -

输出

现在，我们在 Python 中编译上述代码，成功编译后运行它。输出如下：

0 - 1 - 2 - 0
0 - 1 - 5 - 3 - 4 - 2 - 0 - 3 - 5 - 0

上面的代码列出了每个顶点的边数。这是不必要的，因为我们仍然并排保留名称。我们刚刚删除了 edge_count 数组的创建。此算法将 'if edge_count[current_v]' 替换为 'if adj[current_v]'。

上面的代码将第一个或初始节点推入堆栈两次。虽然我们正确地收集了结果，但该方法需要更清晰、更有效。通过将下一个顶点添加到堆栈而不是当前顶点来解决此问题。在测试算法部分，邻接名称“adj1”和“adj2”的开头略有不同。药剂也得到了改善。改进后的代码如下。

程序代码

现在，我们给出了 Hierholzer 算法的改进程序代码。在这里，我们在 Python 中使用 Hierholzer 算法来打印给定有向图的欧拉回路。代码如下 -

输出

现在，我们在 Python 中编译上述代码，成功编译后运行它。输出如下：

0 - 1 - 2 - 0
0 - 1 - 5 - 3 - 4 - 2 - 0 - 3 - 5 - 0