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.

CodePudding user response：

.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);