C++ Fleury 算法用于打印欧拉路径或回路

Fleury 算法 是解决图中欧拉路径和回路的最常用方法之一。它提供了一种系统的方式来遍历图的边，每条边仅访问一次。欧拉路径包含所有边，而欧拉回路是一个闭环，两者都代表对图的边的完整覆盖。然而，这些路径和回路只有在图中固有的特定条件下才能识别。

Fleury 算法执行对图的系统搜索，以找到欧拉路径或回路。然后，它会遍历边，确保每条边只访问一次，同时保持图的连通性。当有多种选择时，算法会智能地选择那些不充当桥梁的边，从而防止图分裂成不连通的组件。

Fleury 算法用于无向图的欧拉路径和回路

这是 Fleury 算法的简单版本。Fleury 算法 用于发现无向图中的欧拉路径和回路。它确保在欧拉回路中每条边恰好经过一次，在欧拉路径中则经过两次。算法从选择起始顶点开始，然后选择具有最少替代的边，避免桥梁以防止过早断开。

重复此过程直到所有边都被遍历，算法就形成了一条覆盖每条边一次的路径或回路。这种简洁性和效率使 Fleury 算法成为研究无向图欧拉特征的有用工具。

程序

输出

Eulеrian Path or Circuit: Graph has no Eulеrian path or circuit.

说明

提供的 C++ 代码实现了 Fleury 算法，用于查找无向图中的欧拉路径或回路。该算法旨在仅一次遍历图中的每条边，形成欧拉路径（如果恰好有两个奇数度顶点）或欧拉回路（如果所有顶点都是偶数度）。

• 图表示

算法首先使用邻接表来表示图。邻接表是一种数据结构，其中每个顶点都维护一个相邻顶点列表。在 C++ 中，代码使用一个 Graph 类来封装这种结构。构造函数设置顶点数，并使用 addEdge 方法添加边到图中。

• 欧拉路径和回路条件

在深入研究算法本身之前，验证给定图是否满足欧拉路径或回路的要求至关重要。Fleury 算法要求图中所有顶点度数都是偶数（如果是欧拉回路），或者恰好有两个顶点的度数是奇数（如果是欧拉路径）。在算法开始时进行此检查，以确保图适合后续遍历。

• Fleury 算法概述

Fleury 算法基于不遍历桥梁（移除后会断开图的边）的原理进行图的导航。其核心是，算法的主循环从当前顶点选择下一条边，将其从图中删除，然后移动到边的另一端。重复此过程直到覆盖所有边。该算法使用堆栈来维护访问顶点的顺序。

• 避免桥梁

Fleury 算法的一个重要元素是在遍历过程中避免桥梁。桥梁是指其移除会增加图中连通分量数量的边。为确保算法不会意外地创建桥梁，isValidNextEdge 函数会检查移除边 (u, v) 是否会断开图的连接。

它通过进行深度优先搜索 (DFS) 并计算边移除前后可达顶点的数量来实现。如果数量保持不变，则可以安全地遍历该边。

• 深度优先搜索 (DFS) 计数

dfsCount 函数使用深度优先搜索来确定从给定顶点可达的顶点数量。它用于确认移除一条边是否会断开图。这种计数机制对于确保算法的决策不影响图的连通性至关重要。

• 遍历和堆栈管理

Fleury 算法的主循环始终选择并遍历边，并更新堆栈。如果一个顶点没有更多边了，它就被认为是欧拉路径或回路的一部分，算法通过弹出堆栈中的最后一个顶点来回溯。遍历一直持续到所有边都被覆盖。

• 输出

最后，算法打印遍历操作期间访问的顶点序列。这个序列根据初始条件，等同于图中的欧拉路径或回路。

• 示例图和输出

在提供的示例中，使用了一个具有四个顶点和特定边的图来演示该算法。图的顶点为 0、1、2 和 3。边连接 0-1、0-2、1-2 和 2-3。输出定义了从指定顶点开始的欧拉路径或回路。

复杂度分析

时间复杂度

图初始化（构造函数）

构造函数为图提供了几个顶点，并设置了邻接表。此操作的时间复杂度为O(V)，其中 V 是顶点的数量。

添加边（addEdge）

边插入还需要修改两个顶点的邻接表集。最坏的情况下，当每个顶点的度数恒定时，时间复杂度为 O(1)。

删除边（removeEdge）

当删除一条边时，意味着从两个顶点的邻接表中删除条目。然而，在最复杂的情况下，当每个顶点的度数恒定时，时间复杂度为 O(1)O(1)。

深度优先搜索 (DFS)： 可访问的顶点通过DFS 操作计算。然而，在所有顶点都可以从其他顶点到达的最坏情况下，时间复杂度可能达到O(V + E)，其中 V 是节点数，E 是边数。

Fleury 算法 (fleuryAlgorithm)

该方法的基本阶段是选择边、删除它们以及运行 DFS。每一步，它要么执行 DFS (O(V + E))，要么从邻接表中弹出边 (O(1))。因此，复杂度为O(V * (V+E))，其中 V 是顶点数，E 是边数。

最后，时间复杂度为O(V * (V + E))，这取决于 DFS 过程。

空间复杂度

图表示

图表示的空间复杂度包括存储邻接表。最坏的情况下，当没有重复边时，空间复杂度为O (V + E)，其中 V 是顶点的数量，E 是边的数量。

DFS 堆栈

DFS 遍历使用一个堆栈来维护访问过的顶点。最坏的情况下，堆栈的大小可能为 V，导致空间复杂度为O(V)。

附加数据结构

其他结构，如用于记账的数组和向量，也对整体空间复杂度有贡献。然而，最坏情况下，这些数据结构的空间需求为O(V)。

最后，空间复杂度由图表示和其他数据结构决定，结果为O (V+ E)。

欧拉路径和回路的概念可以应用于有向图。在有向图中，Fleury 算法的一个变体可能包括考虑顶点的入度和出度来确定是否存在欧拉路径或回路。

Fleury 算法用于有向图，经过调整以考虑顶点的入度和出度。关键思想是遍历边并保持欧拉性质。

入度和出度的概念对于建立欧拉路径或回路的逻辑非常重要。与无向图不同，无向图的边是双向的，有向图的边具有指定的起始和结束顶点。

有向图的欧拉路径和回路

有向图中的欧拉路径是恰好遍历一次有向边的路径。而欧拉回路是以同一顶点开始和结束，恰好访问一次所有有向边的回路。

入度和出度

在有向图中，对于每个顶点，入度表示指向它的边的数量，而出度表示指向它的边的数量。

要存在欧拉路径，最多只能有一个顶点满足 (出度+1) = 入度，并且最多只能有一个顶点满足入度 + 1 = 出度。所有其他顶点都需要满足入度等于出度。

对于欧拉回路，每个顶点都必须满足入度等于出度。

程序

输出

Eulеrian Path or Circuit: Graph has no Eulеrian path or circuit.

说明

上述 C++ 代码实现了 Fleury 算法用于有向图。在这种情况下，Fleury 算法是经典方法在有向图中寻找欧拉路径或回路的改编。该算法在考虑顶点入度和出度的情况下，恰好遍历每条边一次。

• 图初始化（构造函数）

Graph 类封装了有向图的形式和函数。它还有私有成员，包括顶点数 (V) 和邻接表 (adj)。邻接表是向量的向量，表示顶点之间的有向边。

• 构造函数

构造函数根据给定的顶点数创建图，并根据顶点数初始化邻接表。

• addEdge(u, v)

addEdge 方法在顶点 u 和 v 之间创建有向边。它更新邻接表以反映有向关系。

图是用固定数量的顶点构建的；因此，时间复杂度为O (V)。

• 添加边（addEdge）

边是邻接表的修改，在最坏（稀疏图）情况下，其时间复杂度为 1。

• 删除边（removeEdge）

删除边是指删除邻接表中的条目。

• 欧拉路径或回路条件检查

寻找欧拉路径或回路的循环的时间复杂度为O(V)，其中 V 是顶点的数量。

• Fleury 算法 (fleuryAlgorithmDirected)

算法的核心是通过遍历图并确保每条边都是有效的来体现。最坏情况下，其复杂度可能为O(V^2)，其中 V 是顶点的数量。

• isValidNextEdge 方法

检查下一条边的有效性需要遍历邻接表，在最坏情况下，其复杂度为O(d)，其中 d 是顶点的最大度数。

整体时间复杂度由遍历步骤决定，在最坏情况下为 O(V^2)，其中 V 是顶点的数量。

空间复杂度

图表示

图表示的空间复杂度包括存储邻接表。在最坏情况下（稠密图），其复杂度为O(V^2)，V 是顶点的数量。

DFS 堆栈

DFS 遍历使用一个堆栈来记住访问过的顶点。在最坏情况下，堆栈的大小可能为 V，导致空间复杂度为O(V)。

附加数据结构

使用向量和布尔数组的附加数据结构用于计费，并增加了空间复杂度。这些记录结构最多需要O(V)空间。

图表示支配着总空间复杂度；在最坏情况下，其复杂度为O(V^2)，其中 V 是顶点的数量。

Dijkstra 算法结合 Fleury 思想（欧拉路径）

Dijkstra 算法和Fleury 思想的结合，用于在一个 -步过程中找到欧拉路径。首先，使用 Dijkstra 算法确定图中两个奇数度顶点之间的最短路径。这一步保证了通过以最优方式连接标准度顶点，使图变成欧拉图。一旦确定了最短路径，就通过并入这些计算出的路径来调整图，将其变成欧拉图。

然后，应用 Fleury 算法在修改后的图中找到欧拉路径。Fleury 算法的特点是所有边都被恰好遍历一次，同时不遍历任何桥梁边。这种组合方法通过结合 Dijkstra 高效的路径查找和 Fleury 算法用于遍历欧拉路径，为具有均匀度顶点的图中的路径优化和欧拉路径确定问题提供了全面的解决方案。

程序

输出

Eulеrian Path: 1 3 4 3 4 2 4 3 2 3 1 2 4 2 3 2 1 3 1 2 0 2 1 0 1 0 2 0 1 

时间复杂度

鉴于 Dijkstra 算法、combineDijkstraAndFleury 中的重要循环以及 Fleury 算法的时间复杂度，总体时间复杂度由其中最高者决定。因此，总体时间复杂度为O(((V+E) * log(v)))。

空间复杂度

总空间复杂度根据图表示、Dijkstra 算法、组合以及 Fleury 算法的空间复杂度中的最高者计算。因此，稠密图在最坏情况下的总体空间复杂度为O(V^2)，稀疏图为O(V+E)。