欧拉路径
高级欧拉路径问题是"一笔画"问题的图论形式化。
// 算法讲解
欧拉路径
输入节点数和无向边，观察 Hierholzer 算法求欧拉路径。
待机
速度 中
待机 ⌨1void hierholzer(int u, vector<vector<pair<int,int>>>& adj,
2 list<int>& path) {
3 while (!adj[u].empty()) {
4 auto [v, id] = adj[u].back();
5 adj[u].pop_back();
6 hierholzer(v, adj, path);
7 }
8 path.push_front(u);
9}
复杂度分析
时间 O(V + E)
空间 O(V + E)
最优 O(V + E)
最坏 O(V + E)
算法讲解
欧拉路径要求经过图中每条边恰好一次。欧拉回路要求 additionally 起点与终点相同。
无向图存在欧拉回路当且仅当所有顶点度数为偶数且连通；存在欧拉路径当且仅当恰好有两个奇度顶点。
Hierholzer 算法用 DFS 从起点出发，每当无路可走时回溯并将节点加入路径，最终逆序输出即为欧拉路径。
它在 DNA 序列拼接和邮路问题中有直接应用。