编写一个函数，用于在一个图中进行深度优先搜索（DFS）。图以邻接表的形式给出，节点编号从0开始。函数应接受图和一个起始节点作为参数，并打印出访问顺序。

Question

编写一个函数，用于在一个图中进行深度优先搜索（DFS）。图以邻接表的形式给出，节点编号从0开始。函数应接受图和一个起始节点作为参数，并打印出访问顺序。

function dfs(graph, start) {  
  // graph 是一个对象，其属性是节点，值是包含相邻节点的数组  
  // 例如: {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}  
  // 这里的 graph[2] 有一个错误，它不应该包含自己作为邻居  
  // 你的代码，需要包括一个 visited 数组来跟踪访问过的节点  
}  
  
const graph = {  
  0: [1, 2],  
  1: [2],  
  2: [0, 3],  
  3: []  
};  
  
dfs(graph, 2); // 输出可能包括 2, 0, 1, 3，但顺序可能因实现而异

Answer 1

function dfs(graph, startNode) {
            const visited = new Set(); // 用于记录已访问的节点
            const stack = [startNode]; // 初始化栈，添加起始节点
        
            while (stack.length > 0) {
                const currentNode = stack.pop(); // 从栈中弹出一个节点
                if (!visited.has(currentNode)) { // 如果节点未被访问过
                    console.log(currentNode); // 输出当前节点
                    visited.add(currentNode); // 标记为已访问
                    // 将当前节点的邻居节点添加到栈中
                    stack.push(...graph[currentNode].filter(neighbor => !visited.has(neighbor)));
                }
            }
        }
        // 示例使用：
        const graph = {  
            0: [1, 2],  
            1: [2],  
            2: [0, 3],  
            3: []  
        };  
        dfs(graph, 2); // 从2开始深度优先搜索