JS中基于邻接表的图DFS遍历函数失效，求修正方案

你的代码存在多个核心逻辑错误，导致无法正常执行DFS遍历，以下是问题点和修正方案：

原代码的核心问题 #

• 重复压入起始节点：const queue = [start]; queue.push(start); 导致起始节点被重复加入栈，会被处理两次
• 遍历对象错误：循环遍历的是栈的长度而非当前节点的邻接边列表，完全偏离DFS逻辑
• 缺少已访问节点记录：没有维护访问标记，会导致节点被重复遍历，甚至陷入死循环
• 访问判断逻辑错误：!vertex[graph[i]]的写法完全不符合需求，vertex是节点编号，graph[i]也不是当前节点的邻接节点
• 递归与迭代逻辑混乱：函数同时混用递归和迭代，且递归调用时缺失graph参数，流程彻底混乱

修正后的两种实现方案 #

方案1：递归版DFS（更简洁直观）

var graph = {
    1: [2, 4],
    2: [1, 3],
    3: [2, 4],
    4: [1, 3] // 修正原代码的笔误：原4的邻接表是[1,4]，自环无意义，改为[1,3]
};

function dfsRecursive(start, graph, visited = new Set()) {
    // 标记当前节点为已访问
    visited.add(start);
    console.log('访问节点:', start); // 输出访问节点，验证遍历流程

    // 遍历当前节点的所有邻接节点
    for (const neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            dfsRecursive(neighbor, graph, visited);
        }
    }
}

// 调用示例
dfsRecursive(1, graph);

方案2：迭代版DFS（符合你原代码想写迭代的思路）

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

function dfsIterative(start, graph) {
    const stack = [start];
    const visited = new Set();

    while (stack.length > 0) {
        const vertex = stack.pop();
        // 未访问过的节点才处理
        if (!visited.has(vertex)) {
            visited.add(vertex);
            console.log('访问节点:', vertex);

            // 倒序压入邻接节点，保证遍历顺序和递归版一致（栈是后进先出）
            for (let i = graph[vertex].length - 1; i >= 0; i--) {
                const neighbor = graph[vertex][i];
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

// 调用示例
dfsIterative(1, graph);

关键修改说明 #

• 新增visited集合：用来记录已访问节点，彻底避免重复遍历和死循环
• 修正遍历逻辑：针对当前节点的邻接表graph[vertex]遍历，而非栈的长度
• 分离递归与迭代逻辑：两种实现方式二选一，不要混合使用
• 修正邻接表笔误：原节点4的自环[1,4]无意义，改为合理的邻接节点[1,3]（如果是业务需求的自环可以保留，但需要在遍历中判断跳过）

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