一、项目背景详细介绍
在图论（Graph Theory）中，欧拉路径（Euler Path）和欧拉回路（Euler Circuit）是一类非常经典且重要的问题。
该问题最早由数学家欧拉（Leonhard Euler）在研究“哥尼斯堡七桥问题”时提出，被公认为：
图论的起点问题
在实际工程和算法应用中，欧拉路径 / 回路广泛应用于：
网络拓扑分析
路径规划与连通性分析
编译器状态机遍历
DNA 序列拼接
图像轮廓跟踪
字符串重排问题（De Bruijn 图）
从学习角度看，该问题具有非常高的教学价值：
能综合考察图的存储结构
深度理解度数、连通性
熟悉DFS / 递归思想
是从“图的基础”走向“图算法实战”的关键节点
本项目目标是：
使用 C++ 从零实现对无向图 / 有向图的欧拉路径与欧拉回路判定及构造
二、项目需求详细介绍
2.1 功能需求
支持无向图
支持欧拉路径 / 欧拉回路的：
判定
实际路径构造
使用经典Hierholzer 算法
输出一条合法的欧拉路径 / 回路（若存在）
2.2 技术要求
编程语言：C++
图的存储方式：
邻接表
算法要求：
时间复杂度 O(E)
代码注释详尽，便于教学
2.3 设计要求
面向教学与博客输出
所有代码集中在一个代码块
使用注释模拟文件结构
不拆分代码块
逻辑清晰，可逐行讲解
三、相关技术详细介绍
3.1 欧拉路径与欧拉回路定义
欧拉路径（Euler Path）
在图中，恰好经过每一条边一次的一条路径。
起点和终点可以不同
欧拉回路（Euler Circuit）
在图中，恰好经过每一条边一次，并回到起点的一条路径。
起点 = 终点
3.2 无向图中存在条件
欧拉回路存在条件
图是连通的（忽略度为 0 的点）
所有顶点的度数都是偶数
欧拉路径存在条件
图是连通的
恰好有两个顶点的度数为奇数
路径从一个奇度点开始，到另一个奇度点结束
总结表格
| 类型 | 奇度顶点数量 |
|---|---|
| 欧拉回路 | 0 |
| 欧拉路径 | 2 |
| 都不存在 | 其他 |
3.3 Hierholzer 算法思想
Hierholzer 算法是构造欧拉路径 / 回路的经典算法，其核心思想是：
从起点出发，不断走“未使用的边”，走不动就回溯
算法特点：
使用 DFS / 栈
每条边只访问一次
时间复杂度 O(E)
3.4 算法整体流程
判断是否存在欧拉路径 / 回路
选择起点：
若有奇度点，从奇度点开始
否则从任意非零度点开始
执行 Hierholzer DFS
回溯时记录路径
最终路径逆序即为答案
四、实现思路详细介绍
4.1 图的数据结构设计
使用邻接表
每条无向边存两次
使用
used标记防止重复使用边
4.2 起点选择策略
若存在 2 个奇度点 → 欧拉路径 → 从其中一个开始
若不存在奇度点 → 欧拉回路 → 任意点开始
4.3 DFS 构造路径
深度优先遍历未使用的边
边用完后，将当前顶点加入路径
最终路径需要反转
4.4 正确性保证
每条边仅被访问一次
回溯顺序保证边全部覆盖
满足欧拉路径定义
五、完整实现代码
/**************************************************** * 文件名：EulerPath.cpp * 描述：C++ 实现欧拉路径 / 欧拉回路（无向图） ****************************************************/ #include <iostream> #include <vector> #include <algorithm> using namespace std; /**************************************************** * 边结构 ****************************************************/ struct Edge { int to; // 目标顶点 int id; // 边编号 }; /**************************************************** * 图类 ****************************************************/ class Graph { public: Graph(int n) : n(n) { adj.resize(n); degree.resize(n, 0); } /************************************************ * 添加无向边 ************************************************/ void addEdge(int u, int v) { adj[u].push_back({v, edgeCount}); adj[v].push_back({u, edgeCount}); degree[u]++; degree[v]++; used.push_back(false); edgeCount++; } /************************************************ * 判断并寻找欧拉路径 / 回路 ************************************************/ bool findEulerPath(vector<int>& path) { int start = -1; int oddCount = 0; // 统计奇度顶点 for (int i = 0; i < n; ++i) { if (degree[i] % 2 == 1) { oddCount++; start = i; } } // 不满足条件 if (!(oddCount == 0 || oddCount == 2)) return false; // 欧拉回路：任选一个非零度点 if (oddCount == 0) { for (int i = 0; i < n; ++i) { if (degree[i] > 0) { start = i; break; } } } dfs(start, path); // 所有边都应被使用 if (path.size() != edgeCount + 1) return false; reverse(path.begin(), path.end()); return true; } private: int n; int edgeCount = 0; vector<vector<Edge>> adj; vector<int> degree; vector<bool> used; /************************************************ * Hierholzer DFS ************************************************/ void dfs(int u, vector<int>& path) { for (auto& e : adj[u]) { if (!used[e.id]) { used[e.id] = true; dfs(e.to, path); } } path.push_back(u); } }; /**************************************************** * 测试示例 ****************************************************/ int main() { Graph g(5); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(1, 3); g.addEdge(3, 4); g.addEdge(4, 1); vector<int> path; if (g.findEulerPath(path)) { cout << "存在欧拉路径 / 回路：" << endl; for (int v : path) cout << v << " "; cout << endl; } else { cout << "不存在欧拉路径或回路" << endl; } return 0; }六、代码详细解读（仅解读方法作用）
addEdge：添加无向边并维护度数findEulerPath：判定条件并构造欧拉路径dfs：Hierholzer 算法核心，实现边的遍历used：防止同一条边被重复访问path：逆序记录最终路径
七、项目详细总结
通过该项目，你已经系统掌握：
欧拉路径 / 欧拉回路的数学条件
图的度数与连通性分析
Hierholzer 算法的完整实现
图算法中“判定 + 构造”的标准模式
图论问题的工程化实现思路
这是从：
图结构基础 → 图算法实战
的关键跃迁点。
八、项目常见问题及解答
Q1：为什么要在 DFS 回溯时加入路径？
A：确保子路径已完整遍历，符合 Hierholzer 算法思想。
Q2：为什么路径长度是 edgeCount + 1？
A：欧拉路径经过 E 条边，必然经过 E+1 个顶点。
Q3：有向图如何处理？
A：需要判断入度 = 出度（回路）或差为 1（路径）。
九、扩展方向与性能优化
支持有向图欧拉路径
输出具体边序列
非递归栈实现（避免深递归）
大规模图优化（内存池）
De Bruijn 图实战应用
