Stack implementation of DFS. All test cases work except the first

Question

From https://structy.net/problems/largest-component

Write a function, largestComponent, that takes in the adjacency list of an undirected graph. The function should return the size of the largest connected component in the graph.

The problem is this code works for all test cases except the first one. And i do not want to solve this with the recursive DFS method i want to use the stack or queue DFS method.

The main function

const largestComponent = (graph) => {
    //init the largest count variable to 0
    let largest=0;
    // use a global set data structure to keep track of visited nodes
    let visited =  new Set();
        
    //loop through graph object and send each node to DFS function
    for (node in graph) {
        //if node has been visited then skip to next node
        if(visited.has(String(node))) continue;
    
        let currentCount = DFS(graph, node, visited);
        
        // get largest count per iteration
        largest = Math.max(largest, currentCount);
    
    }
    // return result
    return largest;
}

The depth first search function

const DFS = (graph, node, visited) => {
        
    // initiate count for neighbors of current node but also count current node so init to 1
    let currentCount = 1;
    
    // populate stack with node
    let stack = [node];
    
    //loop for as long as stack isn't empty
    while(!!stack.length){
   
        // get current node from stack
        let current = stack.pop();
            
        // mark node as visited
        visited.add(String(current));
        
        // loop through neighbors of node
        for( neighbor of graph[current]){

            // if neighbors have been visited already then skip them
            if(visited.has(String(neighbor))){
                continue;
            } else {
                // add neighbor to count
                currentCount++;
                    
                // add the next neighbor to stack
                stack.push(neighbor);
            }
        }
    }
    // return count of connected components for current node
    return currentCount;
}

Test case 1

console.log(largestComponent({
  0: ['8', '1', '5'],
  1: ['0'],
  5: ['0', '8'],
  8: ['0', '5'],
  2: ['3', '4'],
  3: ['2', '4'],
  4: ['3', '2']
})) // should give -> 4

Test case 2

console.log(largestComponent({
  1: ['2'],
  2: ['1','8'],
  6: ['7'],
  9: ['8'],
  7: ['6', '8'],
  8: ['9', '7', '2']
})); // should give  -> 6

Test case 3

console.log(largestComponent({
  3: [],
  4: ['6'],
  6: ['4', '5', '7', '8'],
  8: ['6'],
  7: ['6'],
  5: ['6'],
  1: ['2'],
  2: ['1']
})); // should give -> 5

Test case 4

console.log(largestComponent({
  0: ['4','7'],
  1: [],
  2: [],
  3: ['6'],
  4: ['0'],
  6: ['3'],
  7: ['0'],
  8: []
})); // should give -> 3

Answer 1

Cause

What happens in Test case 1 is that you are counting 8 twice (once when current is 0 and once when current is 5).

Step by step:

1. Current node is 0, currentCount=1, stack=[], visited=[]
   • Mark 0 as visited -> [0]
   • Add to stack: 8, 1, 5 -> [8, 1, 5]
   • Current count becomes: 1 + 3
2. Current node is 5, currentCount=4, stack=[8, 1] (pop 5), visited=[0]
   • Mark 5 as visited -> [0, 5]
   • Add to stack: 8 (0 is visited, but 8 still not) -> [8, 1, 8]
   • Current count becomes: 4 + 1 here is the problem

Solution

This can be solved changing three things:

1. Count nodes when visited (not when checking neighbors).
2. As a consecuense of point 1, start the currentCount variable at 0.
3. Check if the current node poped from stack hasn't been visited.

Code

The final code will be like this:

const largestComponent = (graph) => {
    //init the largest count variable to 0
    let largest=0;
    // use a global set data structure to keep track of visited nodes
    let visited =  new Set();
        
    //loop through graph object and send each node to DFS function
    for (node in graph) {
        //if node has been visited then skip to next node
        if(visited.has(String(node))) continue;
    
        let currentCount = DFS(graph, node, visited);
        
        // get largest count per iteration
        largest = Math.max(largest, currentCount);
    
    }
    // return result
    return largest;
}

const DFS = (graph, node, visited) => {

    // count starts at 0, `node` will always be counted in the first iteration
    let currentCount = 0;
    
    // populate stack with node
    let stack = [node];
    
    //loop for as long as stack isn't empty
    while(!!stack.length) {
   
        // get current node from stack
        let current = stack.pop();

        // if current node has been visited then skip to next node
        if (visited.has(String(current))) continue;
        
        // mark node as visited and count it
        visited.add(String(current));
        currentCount++;
        
        // loop through neighbors of node
        for( neighbor of graph[current]){

            // if neighbors have been visited already then skip them
            if(visited.has(String(neighbor))){
                continue;
            } else {
                // add the next neighbor to stack
                stack.push(neighbor);
            }
        }
    }
    // return count of connected components for current node
    return currentCount;
}