如何在Node.js中实现欧拉路径算法？

欧拉路径是一笔画出图中所有边且每条边仅经过一次的路径。如果路径的起点和终点相同，则称为欧拉回路。这个概念不仅在数学竞赛和算法面试中出现，在DNA序列拼接、物流路线规划、电路板布线以及游戏关卡设计等领域也有实际应用。Node.js作为服务端运行时，处理图论问题并不少见，但社区中缺少一个简洁且可直接复用的欧拉路径求解模块。本文将从判定定理出发，逐步实现一个健壮的JavaScript版本欧拉路径求解器，并解释关键工程细节。

欧拉路径的存在性判定

欧拉路径是否存在，取决于图中顶点的度数特征。对于无向图，一个连通图存在欧拉路径的充要条件是：所有顶点的度数均为偶数，此时存在欧拉回路；或者恰好有两个顶点的度数为奇数，此时存在欧拉路径但不存在欧拉回路，且路径必须从其中一个奇度顶点开始，到另一个奇度顶点结束。这里的度数指与该顶点相连的边数。如果无向图不连通，或者奇度顶点数量不是0或2，则欧拉路径不存在。

对于有向图，判定条件需要同时考虑入度和出度。一个有向图存在欧拉路径的充要条件是：所有顶点的入度等于出度，此时存在欧拉回路；或者存在一个顶点出度比入度大1，另一个顶点入度比出度大1，其余顶点入度等于出度，此时存在欧拉路径，起点为出度大的顶点，终点为入度大的顶点。同样要求图在忽略方向后是弱连通的。理解这些判定规则后，就可以用代码快速检查图是否具备欧拉路径，并确定起始顶点。

下面的代码展示了一个针对有向图的判定函数，它接收邻接表 adj，并返回起点编号或 -1。该函数同时计算每个顶点的入度和出度，并用计数器记录不平衡的顶点数量。如果符合所有顶点平衡或恰好两个顶点不平衡的条件，则返回合适的起点；否则返回 -1 表示不存在欧拉路径。

function findStartNode(adj) {
    const n = adj.length;
    const inDegree = new Array(n).fill(0);
    const outDegree = new Array(n).fill(0);
    for (let u = 0; u < n; u++) {
        outDegree[u] = adj[u].length;
        for (const v of adj[u]) {
            inDegree[v]++;
        }
    }
    let startCount = 0;
    let endCount = 0;
    let startNode = 0;
    for (let i = 0; i < n; i++) {
        if (outDegree[i] - inDegree[i] === 1) {
            startCount++;
            startNode = i;
        } else if (inDegree[i] - outDegree[i] === 1) {
            endCount++;
        } else if (inDegree[i] !== outDegree[i]) {
            return -1;
        }
    }
    if (startCount === 0 && endCount === 0) {
        for (let i = 0; i < n; i++) {
            if (outDegree[i] > 0) return i;
        }
        return 0;
    }
    if (startCount === 1 && endCount === 1) {
        return startNode;
    }
    return -1;
}

这段代码并未检查图的连通性，因为连通性可以在后续DFS过程中间接验证：如果DFS结束后访问的边数不等于图中总边数，说明图不连通，欧拉路径自然不存在。对于无向图，判定逻辑类似，但需要统计每个顶点的度数，并检查奇度顶点数量。实际项目中可以根据需要分别实现有向图和无向图的判定函数。

使用Hierholzer算法构造路径

Hierholzer算法是求解欧拉路径的经典线性算法。它的核心思想是：从起点开始进行深度优先遍历，每次访问一条边后立即删除该边，然后递归处理相邻顶点。当一个顶点不再有未访问的出边时，将该顶点压入结果栈。最终将结果栈反转，就得到了欧拉路径的顶点序列。这个算法的巧妙之处在于，它能够自动拼接多个子回路，而无需显式回溯处理。

具体到实现层面，通常使用邻接表存储图，每个顶点对应一个可变的邻居列表。为了高效删除已访问的边，可以将邻接表设计为栈结构，每次弹出尾部元素。对于需要字典序最小的欧拉路径场景，可以对邻居列表排序后从尾部弹出，这样能够优先访问编号较小的邻居。下面是一个基于递归的Hierholzer算法实现，它首先通过 findStartNode 找到起点，然后递归遍历并收集路径。

function eulerianPath(adj) {
    const start = findStartNode(adj);
    if (start === -1) return null;
    const path = [];
    function dfs(u) {
        while (adj[u].length > 0) {
            const v = adj[u].pop();
            dfs(v);
        }
        path.push(u);
    }
    dfs(start);
    path.reverse();
    const edgeCount = adj.reduce((sum, list) => sum + list.length, 0);
    if (path.length - 1 !== edgeCount) return null;
    return path;
}

递归实现虽然直观，但在边数非常大的情况下可能触发调用栈溢出。Node.js 默认的调用栈深度大约在一万层左右，对于包含十万条边的稠密图来说，递归深度很容易超出限制。因此生产环境中更推荐将递归改写为迭代形式。迭代版本使用显式的栈来模拟递归过程，并将路径收集拆分为两个阶段：先通过循环不断深入，直到当前顶点没有出边，然后将该顶点压入结果栈，再回溯到上一个顶点继续处理。

下面给出迭代版本，它使用两个栈：stack 用于模拟DFS调用栈，result 用于存储路径逆序。处理逻辑与递归版本等价，但能够突破调用栈深度限制，适合处理大规模图数据。

function eulerianPathIterative(adj) {
    const start = findStartNode(adj);
    if (start === -1) return null;
    const stack = [start];
    const result = [];
    while (stack.length > 0) {
        const u = stack[stack.length - 1];
        if (adj[u].length > 0) {
            const v = adj[u].pop();
            stack.push(v);
        } else {
            result.push(stack.pop());
        }
    }
    result.reverse();
    const edgeCount = adj.reduce((sum, list) => sum + list.length, 0);
    if (result.length - 1 !== edgeCount) return null;
    return result;
}

迭代版本中，stack 保存当前DFS路径上的顶点，每次循环查看栈顶顶点是否还有可用边。有边则继续前进，无边则说明该顶点的所有出边都已处理完毕，将其移入结果栈。最终反转结果栈即得到正确的欧拉路径顺序。这样既保持了线性时间复杂度，又避免了递归可能带来的性能问题。

处理欧拉回路与多种图类型

欧拉回路可以视为欧拉路径的特殊情况，此时所有顶点的入度等于出度，起点可以任意选择。前面的 findStartNode 函数在检测到所有顶点平衡时，会返回第一个出度大于零的顶点作为起点，这保证了算法能够正确处理欧拉回路。需要注意的是，如果图中存在孤立的空顶点，即没有任何边相连的顶点，它们不影响欧拉路径的存在性，但在输出路径时通常会被忽略，除非路径需要包含这些顶点作为单独节点。

对于无向图的欧拉路径，邻接表的构建方式与有向图不同，每条无向边需要同时添加到两个顶点的邻居列表中。在删除边时，需要从两个方向同时删除，否则会残留无效边。一种常见做法是使用 Map 记录边的访问状态，或者在邻接表中存储边对象引用。为了简化，可以先将无向图转换为有向图处理，但需要保证每条无向边仅被访问一次。另一种方案是使用支持双向删除的邻接表结构，例如用数组存储邻居并在删除时标记已访问。

下面演示一个简单的无向图欧拉路径判定与路径构造的示例。为了双向删除方便，这里使用对象存储每个顶点的邻居数组，并在访问时通过过滤已访问边的方式进行处理。这种方法的时间复杂度会略高于标准Hierholzer算法，但对于大多数中小规模图已经足够。

function buildUndirectedAdj(edges, n) {
    const adj = Array.from({ length: n }, () => []);
    const edgeMap = new Map();
    for (let i = 0; i < edges.length; i++) {
        const [u, v] = edges[i];
        const edgeId = u < v ? `${u}-${v}` : `${v}-${u}`;
        adj[u].push({ to: v, edgeId });
        adj[v].push({ to: u, edgeId });
        edgeMap.set(edgeId, false);
    }
    return { adj, edgeMap };
}
function findUndirectedStart(adj) {
    let oddCount = 0;
    let start = 0;
    for (let i = 0; i < adj.length; i++) {
        if (adj[i].length % 2 === 1) {
            oddCount++;
            start = i;
        }
    }
    return oddCount === 0 || oddCount === 2 ? start : -1;
}

该示例中，每条无向边通过一个唯一的 edgeId 标记，避免在双向邻居列表中重复访问。实际工程中，如果图的结构已知且边数量不大，也可以直接使用递归加边删除的方式，但要注意避免在遍历邻居列表时修改数组导致索引错乱。

测试与边界情况

为了验证实现的正确性，需要设计多组测试用例，覆盖欧拉回路、半欧拉图、不存在欧拉路径以及单顶点图等场景。例如对于有向图 [[1],[2],[0]] 表示 0→1，1→2，2→0 的一个环，其欧拉回路应为 [0,1,2,0]。对于有向图 [[1],[2],[]] 表示 0→1，1→2，欧拉路径应为 [0,1,2]。对于图 [[1],[2],[0],[4],[]] 可能包含不连通部分，算法应检测出边数不匹配并返回 null。

性能方面，基于邻接表的Hierholzer算法时间复杂度为 O(V+E)，其中 V 是顶点数，E 是边数，空间复杂度同样为 O(V+E)。在Node.js环境下，如果图规模达到百万级边，迭代版本依然能够稳定运行，但需要注意内存占用，避免在 reduce 统计边数时额外创建大数组。可以在构建邻接表时就维护一个总边数计数器，这样在最终校验时直接比较即可。

另一个容易忽略的边界是存在自环的情况，即顶点到自身的边。自环会让该顶点的入度和出度同时加1，不影响判定条件，但在路径构造过程中会消耗一条出边并重新回到该顶点。Hierholzer算法天然支持自环，因为自环相当于一个长度为1的回路。测试时可以加入包含自环的图来确保实现没有遗漏。例如有向图 [[0,1],[2],[0]] 中顶点0存在自环，其欧拉路径可能为 [0,0,1,2,0] 或类似顺序。

最终实现可以直接嵌入到Express服务或CLI工具中，接收边列表作为输入，返回路径数组或错误信息。对于需要输出字典序最小欧拉路径的需求，只需在构建邻接表后对每个顶点的邻居列表执行降序排序，然后继续使用栈弹出尾部元素即可。这个技巧利用了栈的LIFO特性，确保每次访问当前可选的最小邻居。

欧拉路径Node.jsHierholzer算法修改时间：2026-09-25 21:45:40