欧拉回路（一笔画）

欧拉回路是图论中的一个经典概念指一条经过图中每条边恰好一次并且起点和终点相同的闭合路径。通俗地讲就是一笔画问题中能够不重复地走完所有边并回到起点的画法。基本定义欧拉回路经过图中每条边恰好一次且闭合的回路。欧拉通路经过每条边恰好一次但不闭合的路径起点和终点不同。欧拉图具有欧拉回路的图称为欧拉图。判定定理无向图一个连通无向图存在欧拉回路当且仅当图中所有顶点的度数均为偶数。一个连通无向图存在欧拉通路不闭合当且仅当图中恰好有 0 个或 2 个奇度数顶点。若有 2 个则它们分别为起点和终点。有向图一个有向图存在欧拉回路当且仅当图是强连通的或忽略方向后连通且各顶点在同一个弱连通分量中并且每个顶点的入度等于出度。一个有向图存在欧拉通路当且仅当最多只有一个顶点的出度 - 入度 1起点最多一个顶点的入度 - 出度 1终点其余顶点入度等于出度且图是弱连通的。常见算法Hierholzer 算法推荐O(E)从起点开始深度优先搜索。沿着边走每走一条边就将其删除或标记已用。当当前节点没有未使用的边时将该节点压入栈中并回溯。最后将栈逆序输出即得到欧拉回路/通路。核心代码无向图示例cppvectorint path; void dfs(int u) { while (!graph[u].empty()) { int v graph[u].top(); // 取一条边 graph[u].pop(); // 删除该边 dfs(v); } path.push_back(u); // 后序记录 } // 最后 reverse(path.begin(), path.end()) 得到正确顺序Fleury 算法每次选择桥边之前需要判断是否破坏图的连通性效率较低O(E²)一般不推荐。应用场景邮路问题中国邮递员问题在带权图中寻找最短闭合路径覆盖所有边。DNA 片段拼接将 DNA 片段视为边重叠部分视为节点寻找欧拉路径完成拼接。电路布线、言语路径等。示例验证无向图正方形四个顶点每个顶点度数为 2存在欧拉回路如 A→B→C→D→A。有向图下图是否存在欧拉回路A→B, B→C, C→A, A→C度数检查A(出2入1), B(出1入1), C(出1入1) → 入度≠出度 → 无欧拉回路但存在欧拉通路从 A 到 C。例题332. 重新安排行程 - 力扣LeetCode正是求有向图的欧拉通路起点固定为 JFK并要求字典序最小。使用 Hierholzer 算法 优先队列或 multiset即可高效解决。