拓展：欧拉回路和汉密尔顿回路算法

# 1. 简介

### 1.1 图论基础知识回顾
在深入讨论欧拉回路和汉密尔顿回路算法之前，我们需要回顾一些图论的基础知识。图是由节点（顶点）和边组成的一种数据结构，常用于模拟网络和关系等实际问题。图可以分为有向图和无向图，有向图中的边是有方向的，而无向图中的边没有方向。

### 1.2 欧拉回路和汉密尔顿回路简介
欧拉回路和汉密尔顿回路是图论中的两个重要概念。欧拉回路是经过图中每条边一次且仅一次，并回到起始节点的路径，而汉密尔顿回路则是经过图中每个节点一次且仅一次的路径。

### 1.3 目的和应用领域
欧拉回路和汉密尔顿回路算法不仅在图论中具有重要地位，也在实际生活中有着广泛的应用。例如，在网络路由、物流规划、DNA测序等领域，这两种算法都扮演着重要的角色。在接下来的章节中，我们将深入探讨这两种算法的原理、实现及应用。

# 2. 欧拉回路算法

**2.1 欧拉路径的概念**
在图论中，欧拉路径是指沿着图的边遍历每条边恰好一次，并且可以经过图中的所有顶点的路径。如果起点和终点相同，则称之为欧拉回路。欧拉路径的存在性判定与路径的奇偶度数有关，对于无向图，存在欧拉路径的前提是所有顶点的度数为偶数或者有且仅有两个顶点的度数为奇数；对于有向图，存在欧拉路径的前提是所有顶点的入度等于出度，或者有且仅有一个顶点的入度比出度大1，有且仅有一个顶点的出度比入度大1。
**2.2 路径存在性判定算法**
1. 对于无向图，通过遍历所有顶点的度数，判断是否满足偶数度数或者最多有两个顶点为奇数度数，即可判断是否存在欧拉路径。
2. 对于有向图，同样遍历所有顶点的入度和出度，判断是否满足入度等于出度或者只有一个顶点的入度比出度大1，有且只有一个顶点的出度比入度大1，即可判断是否存在欧拉路径。
**2.3 Fleury算法**
Fleury算法是一种经典的欧拉回路算法，其基本思想是每一步选择一个桥（割边），直到所有边都被访问。Fleury算法适用于无向图，且时间复杂度为O(V+E)。下面是Fleury算法的Python实现代码：

   def fleury(graph):
       edges = {vertex: set(edges) for vertex, edges in graph.items()}
       def dfs(current):
           while edges[current]:
               next_vertex = edges[current].pop()
               edges[next_vertex].remove(current)
               dfs(next_vertex)
           circuit.append(current)
       # 寻找可作为起点的顶点
       start_vertex = next(iter(graph))
       if sum(len(adj) % 2 for adj in graph.values()) not in [0, 2]:
           return "No Euler Circuit"
       circuit = []
       dfs(start_vertex)
       circuit.reverse()
       return circuit

   graph = {
       'A': ['B', 'C'],
       'B': ['A', 'C', 'D', 'E'],
       'C': ['A', 'B', 'D'],
       'D': ['B', 'C', 'E'],
       'E': ['B', 'D']
   }

   print(fleury(graph))

**2.4 Hierholzer算法**
Hierholzer算法也是一种欧拉回路的经典算法，主要用于有向图和无向图的欧拉回路问题。其基本思想是不断寻找新的路径，直到所有边都被访问。Hierholzer算法的时间复杂度也为O(V+E)，下面是Hierholzer算法的Java实现代码：

   public List<Integer> findEulerCircuit(int[][] graph) {
       List<Integer> circuit = new ArrayList<>();
       Stack<Integer> stack = new Stack<>();
       stack.push(0);
       while (!stack.isEmpty()) {
           int curr = stack.peek();
           if (graph[curr].length == 0) {
               circuit.add(stack.pop());
           } else {
               int next = graph[curr][0];
               stack.push(next);
               graph[curr] = Arrays.copyOfRange(graph[curr], 1,