C++ Hierholzer 算法

图论，作为研究图作为数学实体来表示事物之间成对关系（如朋友、邻居或连接）的学科，处于许多复杂领域的核心，例如社交网络、计算机网络和各种交通系统。图论中有一个分支分析图中路径和图的存在。有很多算法是针对这个问题的，但 Hierholzer 算法无疑是最强大的算法之一，可以检测有向图中的欧拉回路。

想象一个错综复杂的迷宫，蜿蜒的通道通向一个顶点，有向路径暗示着转换到另一个节点的概率。目标是在返回起点时仅一次遍历每一条边。因此，更高级的回路是欧拉回路，它是一个闭合的环。Hierholzer 算法，由瑞士数学家 Carl Hierholzer 在大约两百年前创建，是解决这个问题的绝佳方案。

Hierholzer 算法是欧拉路径和回路理论的一个分支，这是伟大的数学家 Leonhard Euler 在 18 世纪送给科学的礼物。欧拉路径遍历每一条边一次；另一方面，欧拉回路也完成一个完整的回路回到起始顶点。即使是最复杂的网络，其互连也隐藏在复杂的图中。Hierholzer 算法在这些场景中表现得非常出色，因为它提供了一种系统的方法来发现复杂有向网络中的欧拉回路。

在本篇博文中，我们将深入 Hierholzer 算法的核心，揭开它的奥秘，并创建一个 C++ 实现，将它的概念之美转化为实践。我们将从研究构成欧拉回路开始，然后继续探索它们的图论和实际应用。然后，我们将从宏观角度审视 Hierholzer 算法；我们将逐一分解这种方法，以便展示它在理清有向图中的纠葛方面的能力。

之后，我们将转向 C++，将我们的理论知识付诸实践。我们将通过一个接一个的示例指导您实现 Hierholzer 算法。还提供具体的代码示例。在此过程中，我们将处理所有边缘情况，并探索如何在进行大量测试的同时优化过程。

理解欧拉回路

在详细解释 Hierholzer 算法的过程之前，有必要理解欧拉回路的概念及其在图论中的重要性。欧拉回路是图中的一个通常的闭合行走，它最终返回到行走开始的同一个顶点，并且每条边都只遍历一次。虽然如此简洁的定义似乎过于简化了欧拉回路及其在图分析中的使用问题，但它以一种非常有趣的方式融合了复杂性。

• 假设一个图是由相互连接的顶点组成的网络，其中每条边代表两个相邻顶点之间的链接。欧拉回路就是穿过网络的一种路线，它沿着所有边但只遍历一次，并形成一个闭合路径。欧拉路径在许多生活领域都有应用，包括网络路由、电路设计和物流规划。
• 通过展示图在某些条件下可能存在欧拉回路来探索欧拉回路。无向图中存在欧拉回路的要求是每个顶点的度数都必须是偶数；这意味着连接到顶点的边的数量是偶数。通过这种性质，（顶点）（边）图确保了图的每一条边都可以遍历，而不会困在任何一个先前访问过的顶点。
• 然而，我们有有向图，它们的标准稍微复杂一些。一个图存在有向回路的充要条件是所有顶点的入度和出度相等。换句话说，每条边的顶点必须拥有相同数量的进入它的边（入度）和离开它的边（出度）。
• 了解这些先决条件是实现 Hierholzer 算法等算法的重要一步，因为它们为使用算法中使用的类似方法提供了路线图。此外，欧拉回路也是研究图的边和顶点、它们的结构和特征以及可能应用的有用工具。 

Hierholzer 算法概述

Hierholzer 算法是 19 世纪 Carl Hierholzer 创建的图论经典算法之一，它以其简单性和普适性而著称，展示了解决问题方法的优美和强大。该方法以其发明者命名，提供了一种系统的方法来查找网络中存在的定向回路。这些回路在网络中的顶点和边之间引入了广泛的变化。在这里，我们将引导您了解 Hierholzer 算法的复杂性，一层一层地揭开它，直到我们达到其设计的真正本质。

• Hierholzer 算法 是一种 DFS 算法，它通过利用欧拉路径的思想来遍历有向图的边。该算法以平稳的移动通过图，仔细连接边以形成一个闭合路径，该路径确保了每条边都被访问一次。
• 它的天才之处在于它能够成功地遍历有向图，深入到某个节点或循环的最深处，同时密切关注隐藏在其中的欧拉回路。
• 算法将首先选择一个顶点作为起始顶点。该顶点充当行程的起点，算法从这里决定进行一次搜寻欧拉路径的旅行。算法从一个起始顶点（如果已选择）开始。然后，它以系统的方式经过图的各个阶段，使用边将它们连接起来形成一条路径，每次只遍历一条边。
• Hierholzer 算法的关键在于它可以通过识别和利用有向图的某些特性来寻找欧拉回路。它应用了边移除的思想，并迭代地削减图，直到最终的欧拉路径被生成，同时遍历所有边。这种边移除操作保证了每条边仅被访问一次，从而满足了欧拉回路的标准。
• 然后，算法开始运行。在此阶段，算法使用一个堆栈来记住访问过的顶点和遍历过的边。这个堆栈是程序用来回溯并探索其他可能路径以更快找到解决方案的主要数据结构。Hierholzer 算法通过细致地管理堆栈，确保没有边被遗漏，并且生成的回路是欧拉的。
• 就 Hierholzer 算法而言，其引人注目之处在于它能够优雅地处理图中的各种边和循环。与在复杂图结构方面遇到问题的其他算法相比，Hierholzer 算法足够复杂，可以通过将多条边和循环组合到最终的欧拉回路中来克服有向图的复杂性。这一特性凸显了该算法在处理各种图类型方面的潜力，因此适用于各种领域。
• Hierholzer 算法在时间和空间复杂度效率方面表现出色。尽管其精巧的架构和路线逻辑的运行相当复杂，但该算法在时间上是经济的，这使得它可以在经济是关键因素的现实应用中得到应用。
• 该算法的效率源于其迭代修剪图的能力，即在遍历图边并同时形成欧拉回路的同时，删除其他不必要的边。

Hierholzer 算法的 C++ 分步实现

现在，让我们看看如何在 C++ 中实现 Hierholzer 算法。我们将逐步进行代码讲解，并附带说明。

首先，让我们定义必需的数据结构和支持函数

输出

 
Eulerian Cycle: 3 2 1 0 

说明

提供的代码以声明库和数据结构开始，利用它们将实现 Hierholzer 算法的特定步骤。我们有用于通用输入/输出操作的例程，用于存储数组的向量，用于堆栈计算的堆栈，用于排序算法等等。

• 接下来，我们创建一个 Graph 类来可视化有向图。该类将具有表示顶点数量的变量 V 和表示图本身邻接表的 adj。
• 有一个构造函数，通过指定其顶点数量来初始化图。此外，还有一个用于释放内存的析构函数，一个用于添加边的 addEdge 函数，一个用于深度优先搜索的 dfs 函数，以及一个用于识别欧拉回路的 eulerianCycle 函数，这些都是公共成员函数。
• dfs 函数负责对给定顶点 v 进行深度优先搜索 (dfs) 遍历。该函数标记已访问的顶点，调用相邻的顶点，并按访问顺序进行排列和访问。
• eulerianCycle 函数首先进行扫描以创建适当的数据结构，并进行深度优先搜索以将顶点推入堆栈。然后，它通过以相反的顺序重复该过程来获取欧拉回路，正确地移除顶点序列的图。
• 我们有一个 main 函数，其中我们展示了所构建算法的理论。我们创建一个具有 4 个顶点的有向图并生成边以形成回路。下一步是使用 eulerianCycle 函数来检测图中的欧拉回路。
• 最后一步是从算法中释放欧拉回路。这里，回路是欧拉的，其顶点序列为 [3, 2, 1, 0]，这意味着它是反向的。

高级版本

为了编写 Hierholzer 算法实现的更高级版本，我们将为代码添加处理顶点之间的多条边和图中的循环的能力。我们还将处理图中没有欧拉回路的情况。至于其他更改，程序的 main 函数将更改为接受用户输入来生成图。

输出

 
Enter the number of vertices: 4 
Enter the number of edges: 5 
Enter the edges (format: source destination): 
0 1 
1 2 
2 3 
3 0 
0 2 
Eulerian Cycle: 0 1 2 3 0 

说明

类似地，通过提供的 C++ 代码说明了如何使用给定的有向图中的欧拉回路来找到分层回路。为了让您更好地理解这个问题，我们将将其分成几段。在那里，我们将展示它的工作原理并概述它的结构。

• 代码包含 #include 语句，其中 <iostream>、<vector>、<stack>、<algorithm> 和 <unordered_map> 都是代码导入的标准库头文件。它们包含了执行输入/输出操作、实现动态数组和基于堆栈的操作、排序数字以及无序属性容器的函数。
• Graph 类被定义为一个有向图表示类。该类具有私有成员变量，如顶点数 (V) 和邻接列表 (adj)，它们为每个顶点指定一个相关的部分顶点列表。构造函数、用于将边添加到图的 addEdge() 函数、用于深度优先搜索的 findDepthFirstSearch() 函数、用于确定是否存在回路的 hasEulerianCycle() 以及用于查找欧拉回路的 eulerianCycle() 都是公共成员函数。
• 构造函数接受 V 作为参数类型，即顶点数。addEdge 方法将两个顶点 (u 和 v) 连接到邻接列表中，这有助于图的构建。
• 在 dfs 函数中，使用的深度优先搜索算法通过访问过的顶点迭代地遍历图并将它们推入堆栈。这样的函数对于建立欧拉回路和显示图的连通性至关重要。
• hasEulerianCycle 函数告诉图是否是欧拉类型。它对每个顶点执行操作，并验证其入度和出度是否相同。此过程通过确定关心顶点的入边和出边之间的不匹配来测试顶点是否满足此条件。如果存在不匹配，则返回 false，表示不存在欧拉回路。
• EulerianCycle() 函数通过从第一个顶点开始的深度优先搜索遍历来生成欧拉回路。路径的方向从右侧开始，然后向左转以形成回路，遵循顶点的顺序。此方法给出描绘欧拉路径的顶点向量。
• 在 main 函数中，用户输入 V 和 E，它们分别是图的顶点数和边数。应用程序请求输入边，addEdge 方法将其存储在图中。在调用 EulerianCycle 函数查找欧拉回路后，结果将显示在控制台上。

复杂度分析

1. 基本版本

• 时间复杂度
  Hierholzer 算法基本形式的大部分效率取决于最深入的搜索操作（DFS 操作或深度优先搜索），该操作用于查找欧拉链。该算法遍历图，每条边和每个顶点恰好访问一次，其复杂度为 O(V + E)，其中 V 是顶点数，E 是图中的边数。虽然 DFS 的遍历时间使每个顶点和每条边只出现一次，但它们的出现顺序使我们能够快速了解图的相互关联性。
• 空间复杂度
  恒定空间的一般思想包含在时间序列堆栈和图表示中。在最坏情况下，所有顶点都被移除并放入队列，空间复杂度为 O(V)。此外，邻接列表需要 O(V + E) 的空间来保存所有顶点和邻接边的空间。因此，基本变体具有 V + E 的空间复杂度，以优化内存使用并为实际图大小提供优势。

2. 高级版本

• 时间复杂度
  Hierholzer 算法的新版本在图中的循环和边的多重性方面得到了增强。因此，整个算法显示出更明显的复杂度评估。然而，在 hasEulerianCycle 函数的最坏情况下，邻接列表（O(E)）中体现的时间处理会恶化到 O(V*E)。这主要是因为包含检查顶点入度和出度的函数是必须的，所以对所有顶点和附近的边进行完整遍历是必要的。此外，eulerianCycle 方法中的 DFS 遍历具有与 O(V + E) 相同的 O(V + E) 时间复杂度，因此整体时间复杂度等于 O(V * E)。
• 空间复杂度
  尽管升级版本提高了排名，但空间复杂度仍然保持高效。将邻接列表保存为 O(V + E) 的内存空间，将 hasEulerianCycle 保存为 O(1)，因为它只保留恒定的空间。DFS 遍历的时间复杂度将保持 O(V)，因为递归堆栈将存在。这样，新的版本将整个空间复杂度保持在 O(V + E)，从而为图形集合的设置实现了平滑的内存消耗。

结论

最后，C++ 语言中的 Hierholzer 算法在其寻找有向图中的欧拉回路的美感和适用性方面得到了体现。我们主要通过估计其时间和空间复杂度来检查算法在基本和高级版本执行中的核心构建。此外，我们表明该算法对各种结构的网络的表现令人满意。

Hierholzer 算法确实是网络理论家和从业者宝贵的工具，因为它有助于揭示相互关联的网络连接的复杂方面。这种方法可以有效地遍历图，处理大边以及循环，并揭示欧拉回路，以便在网络路由、设计电路或组织交付等不同情况下使用。

即使在高级版本中引入了这种复杂性，Hierholzer 算法仍然是实际图尺寸的可行解决方案，因为它在处理现实世界问题中的图分析问题时具有多功能性和鲁棒性。通过使用其技术，像工程师这样的研究人员能够自信地穿越有向图的复杂路径，解开不同的回路，同时了解图的结构和连接。

最后，随着我们对 Hierholzer 算法的探索结束，我们希望欣赏它的数学杰作，同时也考虑它对图论和现实世界应用的贡献。以 Hierholzer 算法为参考，我们已准备好应对图分析中的任何挑战，并且我们可以进一步了解连接世界和路线的广阔未解之谜。