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.
.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 andSameValueZero(p.[[Key]], key)istrue, returntrue.
- If
Type(x)is different fromType(y), returnfalse.
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);