Code wants a num of connected components, using Set() works but Map() seems to fail to check if a node has been visited. Output is 7, expected is 2

The problem is seeing how many connected components there are given an undirected graph. This is the example input.

connectedComponentsCount({
  0: [8, 1, 5],
  1: [0],
  5: [0, 8],
  8: [0, 5],
  2: [3, 4],
  3: [2, 4],
  4: [3, 2]
}); //Answer should be 2

This is what the graph looks like:

        5 ---
        |    |
   1 -- 0 -- 8 
    
    4 ---
    |    |
    2 -- 3

This is the solution that works

const connectedComponentsCount = (graph) => {
  const visited = new Set();
  let count = 0;
  for (let node in graph) {
    if (explore(graph, node, visited) === true) {
      count += 1;
    }
  }
  return count;
};


const explore = (graph, current, visited) => {
  if (visited.has(String(current))) return false;
      
  visited.add(String(current));
  
  for (let neighbor of graph[current]) {
    explore(graph, neighbor, visited);
  }
  
  return true;
};

But this is the code I’m trying make it work for which instead of Set(), uses Map(). I have a feeling that the if condition is not working right because it’s never hitting false — as in, it’s never able to verify if a node was already visited.

Another question is I’m told that Set has an O(1) lookup and addition. I think another SO page indicated that the time complexity for a Map() is similar, is that true?

const connectedComponentsCount = (graph) => {
  const visited = new Map(); 
  let count = 0 
  for (let node in graph) {
    if(traverse(graph, node, visited)) {
      count += 1
    }
  }
  return count; 
};

const traverse = (graph, currentNode, visited) => {
  if(visited.has(currentNode)) return false; 
  visited.set(currentNode, 'visited')
  for (let neighbor of graph[currentNode]) {   
    traverse(graph, neighbor, visited)
  }
  return true; 
}

I also noted that if I were to console.log(visited.get(currentNode)) after the ‘return false’ line. I ALWAYS get undefined instead of the string ‘visited’ that I’m storing. But if I console.log(visited.get(currentNode) right after doing visited.set(currentNode, ‘visited), it of course returns ‘visited.

I wonder if I’m doing something wrong with the recursion or that I’m building up Map() incorrectly.

>Solution :

.has() checks the value and the type of the key.

24.1.3.7 Map.prototype.has ( key )

4a. If p.[[Key]] is not empty and SameValueZero(p.[[Key]], key) is true, return true.

7.2.11 SameValueZero ( x, y )

1. If Type(x) is different from Type(y), return false.

In the "neighbor" call of traverse() that neighbor is a Number and not a string – but that’s what currentNode is in the .set() call.

One solution would be to cast neighbor into a String (or cast currentNode back into an actual number before adding it)

const traverse = (graph, currentNode, visited) => {
  if(visited.has(currentNode)) return false; 
  visited.set(currentNode, 'visited')
  for (let neighbor of graph[currentNode]) {   
    traverse(graph, neighbor.toString(), visited)
  }
  return true; 
}

Working example:

const connectedComponentsCount = (graph) => {
  const visited = new Map(); 
  let count = 0 
  for (let node in graph) {
    if(traverse(graph, node, visited)) {
      count += 1
    }
  }
  return count; 
};

const traverse = (graph, currentNode, visited) => {
    if(visited.has(currentNode)) return false;
  
  visited.set(currentNode, 'visited')
  
  for (let neighbor of graph[currentNode]) {   
    traverse(graph, neighbor.toString(), visited)
  }
  return true; 
}

const result = connectedComponentsCount({
  0: [8, 1, 5],
  1: [0],
  5: [0, 8],
  8: [0, 5],
  2: [3, 4],
  3: [2, 4],
  4: [3, 2]
}); //Answer should be

console.log(result);