欧拉回路与一笔画（Hierholzer 算法）解析
一、引言
“一笔画”是很多人童年的第一个图论问题：能不能不重复地走遍图形上的每一条线？在信息学竞赛里，它对应一个体系完整、模板性极强的考点——欧拉路径与欧拉回路。从柯尼斯堡七桥问题，到信奥备考中的图论基础，再到 DNA 片段拼接、邮递员路线规划，Hierholzer 算法都是绕不开的核心。
本文用一道原创题讲透：怎样判定一张图能否一笔画，怎样用线性时间把那条路线构造出来。配 C++ / Python 双版代码、考点拆解、复杂度与易错点，以及进阶方向。
二、题目 / 项目目标
【原创题】校园快递巡逻路线
某校区有
n个路口（编号1 ~ n）和m条双向小路。巡逻车希望设计一条路线：从某个路口出发，恰好走遍每条小路一次（路口可以重复经过）。
- 输入：第一行
n m；接下来m行每行u v，表示一条连接路口u、v的双向小路（可能重边、自环）。- 输出：若存在这样的路线，先输出一行
Yes，再输出一行顶点序列（空格分隔，要求字典序最小）；若不存在，输出一行No并简要说明原因（奇度顶点个数不对 / 图不连通）。数据范围：
1 ≤ n ≤ 10^5，1 ≤ m ≤ 2×10^5。
这道题的本质就是判定并构造无向图的欧拉路径 / 欧拉回路，并要求字典序最小——正是竞赛里最常见的“一笔画”模板形态。
三、核心考点
- 定义辨析：欧拉路径经过每条边恰好一次（点可重复），起点终点可不同；欧拉回路是起点终点重合的欧拉路径。关键词是“边”，不是“点”。
- 无向图判定：所有“有度”顶点连通，且奇度顶点个数为
0（回路）或2（通路）。 - 有向图判定：基图（忽略方向）连通；回路要求每个顶点入度 = 出度；通路要求恰有一个顶点出度 = 入度 + 1（起点）、一个顶点入度 = 出度 + 1（终点），其余入度 = 出度。
- Hierholzer 思想：DFS 一路走，无路可走时回溯，把当前点压入路径；所有边走完才记录，最后反转得到答案。
- 复杂度：用边编号 + 访问标记（或
ptr指针优化）可达O(V + E)时间与O(V + E)空间。 - 字典序最小构造：邻接表排序，每次优先选编号最小的邻居，得到的顶点序列即为字典序最小。
四、解法 / 拆解
4.1 先判定，再构造
第一步，统计每个顶点的度数（自环贡献 2 度）。无向图里数奇度顶点个数 odd：
odd == 0：存在欧拉回路，起点任取一个有度的点；odd == 2：存在欧拉通路，起点必须是那两个奇度点之一（取编号较小者，利于字典序）；- 其他情况：直接
No。
第二步，连通性检查（只看度数不为 0 的点）。题目若明说“保证连通”可省，但实战务必查，否则会漏判“图分成几块、每块都满足度数条件”的假阳性。
4.2 Hierholzer 算法
核心三步：选起点 → 沿未走边 DFS，走一条删一条 → 回溯时把点加入答案，最后反转。
“删边”保证每条边只走一次；回溯才记录保证拼出来的是合法回路（先找小环并入主路径）。递归版直观，迭代 + ptr 数组版本可避免 O(deg) 删除开销与递归爆栈。
4.3 Python 解法（字典序最小，递归版）
import sys
def solve() -> None:
data = sys.stdin.read().strip().split()
if not data:
return
it = iter(data)
n = int(next(it)); m = int(next(it))
# 邻接表：存邻居，排序后每次取最小编号 => 字典序最小
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for _ in range(m):
u = int(next(it)); v = int(next(it))
adj[u].append(v); adj[v].append(u)
deg[u] += 1; deg[v] += 1
for i in range(1, n + 1):
adj[i].sort()
# 奇度顶点
odd = [i for i in range(1, n + 1) if deg[i] % 2 == 1]
# 连通性：只看有度的点
def connected() -> bool:
start = next((i for i in range(1, n + 1) if deg[i] > 0), -1)
if start == -1:
return True
seen = [False] * (n + 1)
st = [start]; seen[start] = True
while st:
x = st.pop()
for y in adj[x]:
if not seen[y]:
seen[y] = True; st.append(y)
return all(seen[i] or deg[i] == 0 for i in range(1, n + 1))
if len(odd) not in (0, 2):
print("No（奇度顶点个数不是 0 或 2）"); return
if not connected():
print("No（图不连通）"); return
# 起点：最小奇度点；否则最小有度点
src = odd[0] if odd else next(i for i in range(1, n + 1) if deg[i] > 0)
path: list[int] = []
def dfs(u: int) -> None:
while adj[u]:
v = adj[u].pop(0) # 取最小邻居
adj[v].remove(u) # 双向删除该边
dfs(v)
path.append(u) # 回溯时才记录
dfs(src)
path.reverse()
print("Yes")
print(" ".join(map(str, path)))
if __name__ == "__main__":
solve()
4.4 C++ 解法（字典序最小，递归版）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<vector<int>> adj;
vector<int> deg;
vector<int> path;
void dfs(int u) {
while (!adj[u].empty()) {
int v = adj[u][0];
adj[u].erase(adj[u].begin()); // 删 u->v
auto it = find(adj[v].begin(), adj[v].end(), u);
if (it != adj[v].end()) adj[v].erase(it); // 删反向边 v->u
dfs(v);
}
path.push_back(u); // 回溯记录
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
if (!(cin >> n >> m)) return 0;
adj.assign(n + 1, {}); deg.assign(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
deg[u]++; deg[v]++;
}
for (int i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end());
int odd = 0, src = -1;
for (int i = 1; i <= n; i++)
if (deg[i] % 2) { odd++; if (src == -1) src = i; }
// 连通性检查
int first = -1;
for (int i = 1; i <= n; i++) if (deg[i] > 0) { first = i; break; }
if (first != -1) {
vector<bool> vis(n + 1, false);
vector<int> stk = {first}; vis[first] = true;
while (!stk.empty()) {
int x = stk.back(); stk.pop_back();
for (int y : adj[x]) if (!vis[y]) { vis[y] = true; stk.push_back(y); }
}
for (int i = 1; i <= n; i++)
if (deg[i] > 0 && !vis[i]) { cout << "No（图不连通）\n"; return 0; }
}
if (odd != 0 && odd != 2) { cout << "No（奇度顶点个数不是 0 或 2）\n"; return 0; }
if (src == -1)
for (int i = 1; i <= n; i++) if (deg[i] > 0) { src = i; break; }
dfs(src);
reverse(path.begin(), path.end());
cout << "Yes\n";
for (size_t i = 0; i < path.size(); i++)
cout << path[i] << (i + 1 == path.size() ? "" : " ");
cout << "\n";
return 0;
}
4.5 样例
输入：
6 8
1 2
2 3
3 1
3 4
4 5
5 6
6 4
2 4
各点度数：1:2, 2:3, 3:3, 4:4, 5:2, 6:2，奇度顶点为 {2, 3}（共 2 个），且图连通，存在从 2 到 3 的欧拉通路。程序输出（字典序最小顶点序列）：
Yes
2 1 3 2 4 5 6 4 3
可自行验证：序列相邻点之间恰好对应输入的 7 条边，每条边出现一次。
五、进阶
- 有向图版本：度数改用入度
ind、出度outd；通路要求恰一个outd-ind==1（起点）、一个ind-outd==1（终点）；边只需单向删除。 ptr指针优化：给每个顶点的邻接表维护“下一条待试边”下标，避免erase/remove的O(deg)开销，整体严格O(V + E)，且可改成迭代版防递归爆栈（数据m到10^5时必须用）。- Fleury 算法对比：更早的 Fleury 每次“非到万不得已不走桥”，需判桥，复杂度更高；竞赛几乎一律用 Hierholzer。
- 真实应用：DNA 序列拼接（k-mer overlap 图求欧拉路径）、七桥问题、中国邮递员问题（欧拉回路的加权扩展）。
- 练习推荐：信息学奥赛一本通 1341「一笔画问题」、洛谷 P2731「骑马修栅栏」、洛谷 P1127「词链」。
六、小结与互动
欧拉回路 / 一笔画的套路非常固定：先按度数判存在性（无向奇度 0/2，有向出入度相等或差 1），再查连通性，最后用 Hierholzer 边走边删、回溯记录并反转。把“判定三步走”和“删边 + 反转”两个命门记牢，这类题基本秒杀。
你在刷题时还遇到过哪些“看着像一笔画、实则要绕坑”的题？欢迎在评论区留言，我们下一期可以聊聊有向图 + 字典序最小的综合变形。如果本文对你有帮助，记得点赞收藏，备考路上一起进阶！
📚 免费少儿编程资料（夸克网盘领取）
以下资料来自夸克网盘分享，点击链接可直接保存；若需在 App 内打开，也可复制下方明文链接：
- 全国青少年信息素养大赛复赛集训题目Python&C++.docx
https://pan.quark.cn/s/93995d3cb150 - 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf
https://pan.quark.cn/s/da97b5dbf75d - Python背记手册.pdf
https://pan.quark.cn/s/7568ae9ca92b - Python课程
https://pan.quark.cn/s/a94bf02d00c6 - 2024信息素养大赛图形化复赛集训题答案3-9
https://pan.quark.cn/s/6ccab7ec3cbc - 2025年03月份电子学会考级真题
https://pan.quark.cn/s/4403c4228912 - 2025全国青少年信息素养大赛赛项说明
https://pan.quark.cn/s/d9d0df4a9f29 - 青少儿信息素养大赛编程资料
https://pan.quark.cn/s/4ab6bd83be8a
资料持续更新，关注获取最新分享。
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)