本课时有配套视频讲解，购买后即可观看（永久有效）
欧拉道路与欧拉回路
一、课上练习
编程练习
- 欧拉道路：L49989
二、知识总结
✨ 核心思想
欧拉道路（Eulerian Path）是图中经过每条边恰好一次的路径。欧拉回路（Eulerian Circuit）是起点和终点相同的欧拉道路。
这个问题源于著名的"柯尼斯堡七桥问题"：能否不重复地走遍所有桥？欧拉在 1736 年证明了这是不可能的，由此开创了图论。
核心算法是 Hierholzer 算法，它能在 时间内找到欧拉回路或欧拉道路。
✨ 算法原理
存在条件
无向图：
- 欧拉回路存在：所有顶点的度数都是偶数，且图连通。
- 欧拉道路存在：恰好有 0 个或 2 个奇度顶点，且图连通。若有 2 个奇度顶点，它们分别是起点和终点。
有向图：
- 欧拉回路存在：所有顶点入度 = 出度，且图弱连通。
- 欧拉道路存在：最多一个顶点出度 - 入度 = 1（起点），最多一个顶点入度 - 出度 = 1（终点），其余入度 = 出度，且图弱连通。
Hierholzer 算法
Hierholzer 算法通过 DFS 寻找欧拉回路/道路：
- 从起点出发，沿任意未走过的边走下去。
- 当无路可走时（当前顶点的所有边都已走过），将当前顶点加入结果栈，并回溯。
- 回溯后，如果还有未走过的边，继续沿新的边走。
- 最终结果栈的逆序就是欧拉道路/回路。
关键：使用"当前弧优化"——记录每个顶点下一条要尝试的边的位置，避免重复扫描已删除的边。
✨ 代码实现
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5const int MAXM = 400005; // 无向图边数 × 2
6
7// 链式前向星存图
8struct Edge {
9 int to, nxt;
10 bool used; // 标记边是否已走过
11};
12
13Edge edges[MAXM];
14int head[MAXN], cur[MAXN]; // cur为当前弧优化
15int deg[MAXN]; // 顶点的度
16int edgeCnt;
17int n, m;
18vector<int> path; // 存储欧拉路径
19
20void addEdge(int u, int v) {
21 edges[edgeCnt] = {v, head[u], false};
22 head[u] = edgeCnt++;
23}
24
25void hierholzer(int u) {
26 // 使用栈模拟DFS，避免递归栈溢出
27 stack<int> stk;
28 stk.push(u);
29
30 while (!stk.empty()) {
31 int v = stk.top();
32 bool found = false;
33 // 当前弧优化：从上次位置继续扫描
34 for (int& i = cur[v]; i != -1; i = edges[i].nxt) {
35 if (!edges[i].used) {
36 edges[i].used = true;
37 edges[i ^ 1].used = true; // 无向图：同时标记反向边
38 stk.push(edges[i].to);
39 found = true;
40 break;
41 }
42 }
43 if (!found) {
44 // 无路可走，加入结果
45 path.push_back(v);
46 stk.pop();
47 }
48 }
49}
50
51int main() {
52 ios::sync_with_stdio(false);
53 cin.tie(nullptr);
54
55 cin >> n >> m;
56 memset(head, -1, sizeof(head));
57 edgeCnt = 0;
58
59 for (int i = 0; i < m; i++) {
60 int u, v;
61 cin >> u >> v;
62 addEdge(u, v);
63 addEdge(v, u); // 无向图双向加边
64 deg[u]++;
65 deg[v]++;
66 }
67
68 // 检查欧拉道路/回路是否存在
69 int oddCount = 0, start = 1;
70 for (int i = 1; i <= n; i++) {
71 if (deg[i] % 2 == 1) {
72 oddCount++;
73 start = i; // 从奇度顶点出发
74 }
75 }
76
77 if (oddCount != 0 && oddCount != 2) {
78 cout << "No Eulerian Path or Circuit" << endl;
79 return 0;
80 }
81
82 // 初始化当前弧
83 for (int i = 1; i <= n; i++) cur[i] = head[i];
84
85 hierholzer(start);
86
87 // 检查是否走过所有边
88 if ((int)path.size() != m + 1) {
89 cout << "Graph is not connected" << endl;
90 return 0;
91 }
92
93 // 逆序输出路径
94 reverse(path.begin(), path.end());
95 for (int i = 0; i <= m; i++) {
96 cout << path[i];
97 if (i < m) cout << " ";
98 }
99 cout << endl;
100
101 return 0;
102}1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5
6vector<int> adj[MAXN]; // 邻接表
7int cur_idx[MAXN]; // 当前弧指针
8int inDeg[MAXN], outDeg[MAXN];
9int n, m;
10vector<int> path;
11
12void hierholzer(int u) {
13 stack<int> stk;
14 stk.push(u);
15
16 while (!stk.empty()) {
17 int v = stk.top();
18 if (cur_idx[v] < (int)adj[v].size()) {
19 int w = adj[v][cur_idx[v]++];
20 stk.push(w);
21 } else {
22 path.push_back(v);
23 stk.pop();
24 }
25 }
26}
27
28int main() {
29 ios::sync_with_stdio(false);
30 cin.tie(nullptr);
31
32 cin >> n >> m;
33 for (int i = 0; i < m; i++) {
34 int u, v;
35 cin >> u >> v;
36 adj[u].push_back(v);
37 outDeg[u]++;
38 inDeg[v]++;
39 }
40
41 // 为了字典序最小，对邻接表排序
42 for (int i = 1; i <= n; i++) {
43 sort(adj[i].begin(), adj[i].end());
44 }
45
46 // 检查存在性并确定起点
47 int start = 1;
48 int startNodes = 0, endNodes = 0;
49 for (int i = 1; i <= n; i++) {
50 if (outDeg[i] - inDeg[i] == 1) {
51 start = i;
52 startNodes++;
53 } else if (inDeg[i] - outDeg[i] == 1) {
54 endNodes++;
55 } else if (inDeg[i] != outDeg[i]) {
56 cout << "No Eulerian Path or Circuit" << endl;
57 return 0;
58 }
59 }
60
61 if (startNodes > 1 || endNodes > 1 ||
62 (startNodes == 1 && endNodes != 1)) {
63 cout << "No Eulerian Path or Circuit" << endl;
64 return 0;
65 }
66
67 memset(cur_idx, 0, sizeof(cur_idx));
68 hierholzer(start);
69
70 if ((int)path.size() != m + 1) {
71 cout << "Graph is not connected" << endl;
72 return 0;
73 }
74
75 reverse(path.begin(), path.end());
76 for (int i = 0; i <= m; i++) {
77 cout << path[i];
78 if (i < m) cout << " ";
79 }
80 cout << endl;
81
82 return 0;
83}✨ 执行示例
有向图：4 个顶点，6 条边。
边：1→2, 2→3, 3→1, 1→3, 3→4, 4→1
度数检查：所有顶点入度 = 出度（各为 2），存在欧拉回路。
从顶点 1 出发执行 Hierholzer：
1栈操作过程：
2stk: [1] → 走到2 → stk: [1,2]
3→ 走到3 → stk: [1,2,3] → 走到1 → stk: [1,2,3,1]
4→ 走到3 → stk: [1,2,3,1,3] → 走到4 → stk: [1,2,3,1,3,4]
5→ 走到1 → stk: [1,2,3,1,3,4,1]
6→ 1无边可走，弹出1，path=[1]
7→ 4无边可走，弹出4，path=[1,4]
8→ 3无边可走，弹出3，path=[1,4,3]
9→ 1无边可走，弹出1，path=[1,4,3,1]
10→ 3无边可走，弹出3，path=[1,4,3,1,3]
11→ 2无边可走，弹出2，path=[1,4,3,1,3,2]
12→ 1无边可走，弹出1，path=[1,4,3,1,3,2,1]
13
14逆序：1 → 2 → 3 → 1 → 3 → 4 → 1路径经过每条边恰好一次，起点和终点相同。
✨ 解题步骤详解
- 判断类型：有向图还是无向图？求欧拉回路还是欧拉道路？
- 检查存在性：
- 无向图：数奇度顶点（0个=回路，2个=道路，其他=不存在）。
- 有向图：检查入度出度差。
- 检查连通性：图必须连通（忽略孤立顶点）。
- 确定起点：
- 欧拉回路：任意顶点。
- 欧拉道路（无向图）：从奇度顶点出发。
- 欧拉道路（有向图）：从出度-入度=1 的顶点出发。
- Hierholzer 求路径：使用栈模拟，配合当前弧优化。
- 验证：路径长度应为 （ 条边， 个顶点）。
✨ 常见错误
- 无向图忘记标记反向边：无向图每条边存两次，走一条必须同时标记另一条。用
i ^ 1获取反向边（边从编号 0 开始，成对存储）。 - 连通性未检查：度数条件满足但图不连通时，不存在欧拉路径。
- 起点选择错误：欧拉道路必须从正确的顶点出发。
- 递归版栈溢出：边数很大时递归 Hierholzer 可能爆栈，建议用栈模拟。
- 字典序要求时未排序：需要字典序最小的欧拉路径时，邻接表要排序。
- 当前弧优化遗漏：不用当前弧优化可能导致 退化。
✨ 算法评价
| 指标 | 分析 |
|---|---|
| 时间复杂度 | ，每条边恰好访问一次 |
| 空间复杂度 | |
| 适用场景 | 求欧拉回路/道路、一笔画问题 |
| 实现难度 | 中等，需注意边的标记和当前弧优化 |
| 前置知识 | 图的存储、DFS/栈 |
欧拉路径问题是图论中的经典题型。掌握存在条件的判定和 Hierholzer 算法是解题关键。
三、课后练习
编程练习
- 无序字母对：L50007