如何用JavaScript实现图的所有可能路径查找？附现有代码

你的BFS实现思路没问题，但存在两个核心问题：一是未处理环结构（比如节点4的自环会导致无限生成冗余路径，甚至程序无法终止）；二是用数组shift()操作队列效率极低（数组头部删除是O(n)时间复杂度）。下面给出两种更优的实现方案：

方案一：递归回溯（DFS）—— 内存效率高+逻辑简洁 #

这种方式通过回溯机制复用路径数组，避免不必要的拷贝，同时用visited集合防止循环访问：

let graph = {
    1: [2, 4],
    2: [1, 3],
    3: [2, 4],
    4: [1, 4]
};

function findAllPath(graph, start, end) {
    const paths = [];
    const visited = new Set();

    function backtrack(currentNode, currentPath) {
        if (currentNode === end) {
            paths.push([...currentPath]);
            return;
        }
        visited.add(currentNode);
        for (const nextNode of graph[currentNode]) {
            if (!visited.has(nextNode)) {
                currentPath.push(nextNode);
                backtrack(nextNode, currentPath);
                currentPath.pop();
            }
        }
        visited.delete(currentNode);
    }

    backtrack(start, [start]);
    return paths;
}

console.log(findAllPath(graph, 1, 3));

优势： #

• 仅在找到终点时才复制路径，内存开销远低于原代码的每次路径拷贝。
• 彻底解决环结构导致的无限循环问题，不会生成包含重复节点的冗余路径。
• 递归逻辑直观，代码可读性强。

方案二：迭代BFS优化—— 避免递归栈溢出 #

如果你的图规模很大，递归可能触发栈溢出，可以用迭代BFS实现，同时优化队列操作和环检测：

function findAllPathBFS(graph, start, end) {
    const paths = [];
    // 队列元素：[当前路径, 已访问节点集合]
    const queue = [[[start], new Set([start])]];

    while (queue.length > 0) {
        // 注意：如果要进一步优化效率，可以用双向队列（JS需手动实现），避免shift()的O(n)开销
        const [currentPath, visited] = queue.shift();
        const lastNode = currentPath.at(-1);

        if (lastNode === end) {
            paths.push(currentPath);
            continue;
        }

        for (const nextNode of graph[lastNode]) {
            if (!visited.has(nextNode)) {
                const newVisited = new Set(visited);
                newVisited.add(nextNode);
                queue.push([[...currentPath, nextNode], newVisited]);
            }
        }
    }

    return paths;
}

优势： #

• 迭代方式不会受递归栈深度限制，适合超大图场景。
• 同样通过visited集合避免循环路径，解决原代码的无限循环问题。

总结 #

• 小规模图优先选递归回溯方案，兼顾效率和可读性。
• 大规模图或需避免递归栈溢出时，选优化后的迭代BFS方案。

内容的提问来源于stack exchange，提问作者Sougata Mukherjee