JAVASCRIPT DFS of Graph-CodePudding

I am trying to create an iterative DFS but I can't seem to add items to the visited set? After, I will try to do a recursive DFS. I'm not uite sure what I am doing wrong here. Assistance would be greatly appreciated. <3

const adjList = {
  1: [2, 5],
  2: [1, 3, 5],
  3: [2, 4],
  4: [3, 5, 6],
  5: [1, 2, 4],
  6: [4]
}

function printDepthFirst(start, visited = new Set()) {
  // your code here
  let adj = adjList;


        const stack = [];
        stack.push(start);
        visited.add(start)
        let visitedArr = [];


        while(stack.length) {

            let Node = stack.pop();
            visitedArr.push(Node)
            console.log(" Visited Node: "   Node)
            
            let neighbors = adj[Node]

            
            

            
            for (let i = 0; i < neighbors.length; i  ) {
                if (!visited.has(neighbors[i])) {
                stack.push(neighbors[i]);
                }
            }
            neighbors.forEach(neighbor => visited.add(neighbor))
        }
        console.log("Visited Nodes: "   JSON.stringify([...visited]))
        console.log("VisstedArr: "   visitedArr)
        return false;
    }

console.log("First Test:")
printDepthFirst(3); // Prints 1 through 6 in Depth-first order, starting with 3
                    // One possible solution:  3, 4, 6, 5, 1, 2
console.log("Second Test:")
printDepthFirst(6); // Prints 1 through 6 in Depth-first order, starting with 6
                    // One possible solution:  6, 4, 5, 2, 1, 3
console.log("Third Test:")
printDepthFirst(4); // Prints 1 through 6 in Depth-first order, starting with 4
                    // One possible solution:  4, 6, 5, 2, 1, 3

CodePudding user response：

You're adding the neighbors to the visited set to early: all of them during the first iteration! This means that on the subsequent iterations, none of the other neighbors will be added to the stack. It should be either

for (let i = 0; i < neighbors.length; i  ) {
    if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
        visited.add(neighbors[i]))
    }
}

for (let i = 0; i < neighbors.length; i  ) {
    if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
    }
}
neighbors.forEach(neighbor => visited.add(neighbor))

(Another approach, a bit closer to the recursive version, would be to always add all of the neighbors - possibly just as the whole array - to the stack, and check whether they had already been visited only when popping them from the stack)

Btw, another problem that leads to your code implementing a BFS rather than a DFS is the use of stack.shift(). You're using the array as a queue, not as a stack, it should be stack.pop()!

CodePudding user response：

JSON.stringify is not working for sets because the data stored in the set is not stored as properties.

To properly print set, you should do:

console.log(JSON.stringify([...s]));