java - 有没有一种从无向邻接表中快速找到欧拉环路的方法？

Question

出于测试目的，我使用了以下邻接矩阵:

    A   B   C   D   E   F
A   0   1   1   0   0   0  
B   1   0   1   1   1   0  
C   1   1   0   1   1   0  
D   0   1   1   0   1   1  
E   0   1   1   1   0   1  
F   0   0   0   1   1   0

由此，我可以得到以下邻接表:

A:  B   C 
B:  A   C   D   E 
C:  A   B   D   E 
D:  B   C   E   F 
E:  B   C   D   F 
F:  D   E  

是否有从该列表中找到欧拉回路的快速方法？如果是这样，那么假设我将能够使用所述方法在列表的任何子集中找到可能的欧拉电路是否正确？

感谢您的宝贵时间。

Answer 1

要知道无向图中是否存在欧拉路径，必须满足两个条件:

• 所有非零度的顶点都属于一个连通分量
• 每个顶点的度必须是偶数

例如下图

不允许欧拉回路，因为无法从左子图到达右子图的边缘，反之亦然。

您可以使用 DFS 或 BFS 方法在线性时间内(相对于图的边和顶点的数量)检查图是否为单连通分量。从任何非零度数的顶点开始，检查是否可以到达图中的任何其他顶点(零度数除外，但无论如何您都无法根据定义到达它们)。

完成后，检查每个顶点的度数是否均匀。

此时您知道必须存在欧拉回路。要找到一个，可以使用 Fleury 算法(网络上有很多示例，例如 here )。

Fleury 算法的时间复杂度为 O(|E|)，其中 E 表示边集。但是您还需要在运行算法时检测网桥。您可以使用时间复杂度为 O(|V|+|E|) 的 Tarjan 算法检测桥梁。

所以 Fleury 算法的整体时间复杂度是 O(|E|²)

---

因此从您的相邻列表导出的图表中:

1. 从 A 开始(任意)
2. 从 A 到 B 的旅行(任意)
3. 从 B 到 C 的旅行(任意)
4. 现在您必须前往 D，因为边 A-C 是桥边
5. 从 D 到 B 的旅行(任意)
6. 从 B 到 E 旅行(您别无选择)
7. 从 E 到 F(你不能去 C，因为 E-C 是桥边)

现在你别无选择，所以

1. 从 F 到 D 的旅行
2. 从 D 到 E 的旅行
3. 从 E 到 C 的旅行
4. 从 C 到 A 的旅行

所以欧拉回路是 A-B-C-D-B-E-F-D-E-C-A。