欧拉道路与欧拉回路 (Eulerian Path & Circuit)

基于一笔画定理与度的奇偶判定，利用 Hierholzer 深度优先搜寻回溯算法一气呵成

📖 算法原理：一笔画与奇数度顶点定理

欧拉图（Eulerian Graph）源于著名的哥尼斯堡七桥问题。在一张无向图 $G = (V, E)$ 中：

📐 欧拉通路/回路存在性判定定理（无向图连通图下）

  • 具有欧拉回路的充要条件：图中所有顶点的度数均为偶数（奇数度顶点个数 $N_{odd} = 0$）。
  • 具有欧拉通路的充要条件：图中恰好有 2 个顶点的度数为奇数（奇数度顶点个数 $N_{odd} = 2$）。此时，欧拉通路必须从其中一个奇数度顶点出发，在另一个奇数度顶点结束。
  • 若奇数度顶点个数 $N_{odd} > 2$，则该图绝对不是欧拉图，无法完成一笔画！
奇数度顶点数 $N_{odd}$
0
是否存在欧拉回路
检测中
是否存在欧拉通路
检测中
选择图形并尝试在下方图上依次点击顶点进行“手动一笔画挑战”，或点击“自动一笔画”观看 DFS 逆序回溯合成路径。
👣 当前生成的一笔画序列 (Traverse Sequence)：
空
🕸️ 欧拉流光路径动态几何拓扑网络 (Eulerian Topology Map)
vector<int> path; // 记录欧拉路径倒序结果
bool vis[MAXM];   // 标记边是否已访问

void dfs(int u) {
    for (auto& edge : g[u]) {
        int e_idx = edge.id;
        int v = edge.to;
        if (!vis[e_idx]) {
            vis[e_idx] = true; // 标记此边已用
            dfs(v);            // 深度优先递归推进
        }
    }
    path.push_back(u); // 回溯时将节点推入结果序列
}

void getEulerPath() {
    path.clear();
    memset(vis, 0, sizeof(vis));
    // 从奇数度顶点出发，若全为偶数度则从任意连通点出发
    int start = findStartNode(); 
    dfs(start);
    reverse(path.begin(), path.end()); // 倒序翻转得出正向一笔画路径
}
📋 算法回溯追踪与步骤