欧拉图相关。
- 通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路；
- 通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。
判定
无向图
- 图连通。
- 欧拉回路：所有点度数为偶数。
- 欧拉通路：只有起点和终点度数不为偶数；
有向图
- 欧拉回路：所有点在同一个强连通分量，每个点入度和出度相同；
- 欧拉通路：将有向边视为无向时图连通；起点出度比入度大 $1$ ，终点入度比出度大 $1$ ，其他点入度出度相同。
Hierholzer 算法
求欧拉路径：
- 确定起点；
- 从起点开始搜索，经过一条边后将其删除；
- 所有边都删除后，将其加入栈中；
- 从栈顶到栈底即为答案。