No entiendo los posibles recorridos de gráficos cíclicos, ¿por qué hay una conexión entre el nodo de origen y el de destino en el gráfico?
i) DFS, si se visita un nodo, devolvemos falso
ii) BFS, si se visita un nodo, continuamos (en el bucle)
código de ejemplo (de https://structy.net/problems/undirected-path ):
const undirectedPath = (edges, nodeA, nodeB) => { const graph = buildGraph(edges); return hasPath(graph, nodeA, nodeB, new Set()); } // BFS const hasPath = (graph, src, dst, visited) => { const queue = [src]; while(queue.length > 0){ const current = queue.shift(); if(current === dst) return true; // if it's DFS, do not "continue", instead "return false" - why? if(visited.has(current)) continue; visited.add(current); for(let neighbor of graph[current]){ queue.push(neighbor); } } return false; } const buildGraph = (edges) => { const graph = {}; for(let edge of edges){ const[a, b] = edge; if(!(a in graph)) graph [a] = []; if(!(b in graph)) graph [b] = []; graph[a].push(b); graph[b].push(a); } return graph; } const edges = [ ['i', 'j'], ['k', 'i'], ['m', 'k'], ['k', 'l'], ['o', 'n'] ]; undirectedPath(edges, 'j', 'm'); // -> trueConsidere un gráfico simple con dos nodos:
Hay dos bordes también:
En su enfoque DFS, tiene los siguientes pasos
En resumen, su algoritmo es defectuoso. Tenga en cuenta que esto ni siquiera requiere el caso especial de un borde que se enrolla sobre sí mismo. Todo lo que se necesita es un ciclo que se evalúa antes de alcanzar el objetivo. Además, si por casualidad se comprobó primero el vecino B, habría obtenido un resultado correcto.