xxx 有向图中的欧拉回路（Hierholzer算法）

题目描述：
给定一个有向图，判断该图是否存在欧拉回路，如果存在则找出该回路。欧拉回路是指一条经过图中每条边恰好一次且起点和终点相同的路径。

存在条件：

1. 图是连通的（在忽略边方向的基础无向图上连通）
2. 每个顶点的入度等于出度

解题过程：

步骤1：检查存在性条件
首先需要确认图是否满足欧拉回路的存在条件：

• 检查图的连通性：忽略边的方向，检查基础无向图是否连通
• 检查每个顶点的入度和出度是否相等

# 伪代码示例
def has_euler_circuit(graph):
    # 检查度数条件
    for vertex in graph.vertices:
        if vertex.in_degree != vertex.out_degree:
            return False
    
    # 检查连通性（在基础无向图上）
    return is_connected(convert_to_undirected(graph))

步骤2：Hierholzer算法核心思想
算法基于深度优先搜索，但采用更聪明的方式来构建回路：

1. 从任意顶点开始进行深度优先遍历
2. 当无法继续前进时（当前顶点没有未访问的出边），将该顶点加入回路
3. 回溯到上一个顶点，继续寻找新的路径
4. 最终将所有路径片段组合成完整的欧拉回路

步骤3：算法详细步骤

步骤3.1：数据结构准备

• 使用邻接表表示图
• 维护每个顶点未访问的出边列表
• 使用栈来记录当前路径
• 使用列表存储最终的欧拉回路

def hierholzer(graph):
    # 检查是否存在欧拉回路
    if not has_euler_circuit(graph):
        return None
    
    # 初始化数据结构
    current_path = []  # 栈，记录当前路径
    circuit = []       # 最终回路
    edge_count = {v: len(graph.adj[v]) for v in graph.vertices}
    # 复制邻接表，避免破坏原图
    temp_adj = {v: list(graph.adj[v]) for v in graph.vertices}

步骤3.2：选择起始顶点
可以选择任意顶点作为起点，通常选择有出边的第一个顶点：

current_vertex = next(iter(graph.vertices))

步骤3.3：深度优先遍历构建回路
这是算法的核心部分：

current_path = [current_vertex]
circuit = []

while current_path:
    current_vertex = current_path[-1]
    
    # 如果当前顶点还有未访问的出边
    if temp_adj[current_vertex]:
        # 选择一条出边
        next_vertex = temp_adj[current_vertex].pop()
        # 将下一个顶点加入路径
        current_path.append(next_vertex)
    else:
        # 当前顶点没有未访问的出边，将其加入回路
        circuit.append(current_path.pop())

步骤3.4：理解算法执行过程
让我用一个简单例子说明执行过程：

考虑图：0→1→2→0

• 从顶点0开始：current_path = [0]
• 从0到1：current_path = [0, 1]
• 从1到2：current_path = [0, 1, 2]
• 从2到0：current_path = [0, 1, 2, 0]
• 现在0没有未访问的出边：circuit = [0]
• 回溯到2：circuit = [0, 2]
• 回溯到1：circuit = [0, 2, 1]
• 回溯到0：circuit = [0, 2, 1, 0]

最终回路是逆序的：[0, 1, 2, 0]

步骤4：算法复杂度分析

• 时间复杂度：O(E)，其中E是边的数量
• 空间复杂度：O(E + V)，其中V是顶点数量

步骤5：完整实现示例

class EulerCircuit:
    def __init__(self, graph):
        self.graph = graph
        self.temp_adj = {v: list(neighbors) for v, neighbors in graph.adj.items()}
    
    def find_circuit(self):
        if not self._has_euler_circuit():
            return None
        
        current_path = [next(iter(self.graph.vertices))]
        circuit = []
        
        while current_path:
            current = current_path[-1]
            if self.temp_adj[current]:
                next_vertex = self.temp_adj[current].pop()
                current_path.append(next_vertex)
            else:
                circuit.append(current_path.pop())
        
        return circuit[::-1]  # 反转得到正确顺序
    
    def _has_euler_circuit(self):
        # 检查度数条件
        for vertex in self.graph.vertices:
            if len(self.graph.adj[vertex]) != self.graph.in_degree[vertex]:
                return False
        # 检查连通性（简化，实际需要完整实现）
        return True

步骤6：算法正确性证明
Hierholzer算法的正确性基于：

1. 当图满足欧拉回路条件时，总能找到完整回路
2. 每次回溯时，当前顶点确实没有未访问的出边
3. 最终所有边都被恰好访问一次

步骤7：处理特殊情况

• 如果图不连通，返回空
• 如果存在孤立顶点（没有边），算法仍然有效
• 对于多重图（有重边），需要特殊处理边的计数

这个算法优雅地解决了有向图欧拉回路问题，是图论中一个经典且高效的算法。