El problema es ver cuántas componentes conectadas hay dadas en un gráfico no dirigido. Esta es la entrada de ejemplo.
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 2Así es como se ve el gráfico:
5 --- | | 1 -- 0 -- 8 4 --- | | 2 -- 3Esta es la solución que funciona.
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; };Pero este es el código que estoy tratando de hacer que funcione para el cual, en lugar de Set(), usa Map(). Tengo la sensación de que la condición if no funciona correctamente porque nunca da falso, es decir, nunca puede verificar si ya se visitó un nodo.
Otra pregunta es que me dijeron que Set tiene una búsqueda y adición O(1). Creo que otra página SO indicó que la complejidad del tiempo para un Map() es similar, ¿es eso cierto?
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; }También noté que si fuera a console.log(visited.get(currentNode)) después de la línea 'return false'. SIEMPRE obtengo indefinido en lugar de la cadena 'visitado' que estoy almacenando. Pero si consola.log(visited.get(currentNode) justo después de hacer visited.set(currentNode, 'visited), por supuesto devuelve 'visited.
Me pregunto si estoy haciendo algo mal con la recursividad o si estoy construyendo Map() incorrectamente.
.has() comprueba el valor y el tipo de la clave.
24.1.3.7 Map.prototype.has ( key )
4a. Si
p.[[Key]]no está vacío ySameValueZero(p.[[Key]], key)estrue, devuelvetrue.
- Si
Type(x)es diferente deType(y), devuelvefalse.
En la llamada "vecina" de traverse() , ese neighbor es un Number y no una string , pero eso es lo que es currentNode en la llamada .set() .
Una solución sería convertir al neighbor en una String (o convertir currentNode nuevamente en un número real antes de agregarlo)
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; }Ejemplo de trabajo:
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);