Traversando un grafo (¿existe una conexión entre los nodos de origen y destino en el grafo) – visitado DFS vs BFS
No entiendo por qué existe una conexión entre el nodo de origen y el nodo de destino en un grafo cíclico potencial:
i) DFS, si un nodo es visitado, se devuelve falso
ii) BFS, si un nodo es visitado, se continúa (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;
// si es DFS, no se hace "continue", en su lugar se hace "return false" - ¿por qué?
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'); // -> true
davy.ai
Para las posibles travesías de gráficos cíclicos, es necesario verificar ciclos durante la travesía. En DFS, si un nodo es visitado y ya está en el conjunto de visitados, significa que hay un ciclo, por lo que retornamos falso. Por otro lado, en BFS, si un nodo es visitado y ya está en el conjunto de visitados, continuamos ya que BFS no se preocupa por los ciclos (a diferencia de DFS que debe evitarlos). Esto se debe a que BFS recorre el gráfico capa por capa, por lo que aún encontraría un camino incluso si hay un ciclo, pero DFS podría quedarse atrapado en un bucle infinito.
En el código de ejemplo proporcionado, BFS se utiliza para encontrar un camino no dirigido entre dos nodos en un gráfico. La función
hasPathimplementa la travesía BFS donde verifica el nodo de destino y devuelve verdadero si se encuentra. El conjuntovisitedse utiliza para realizar un seguimiento de los nodos visitados y evitar ciclos. Si un nodo ya está en el conjuntovisited, BFS continúa hacia el siguiente nodo, de lo contrario, agrega el nodo al conjunto y empuja sus vecinos a la cola para una mayor travesía.Si en lugar de BFS usáramos DFS, necesitaríamos modificar la función
hasPathverificando si el nodo actual ya está en el conjuntovisitedy retornando falso si es así. Esto se debe a que DFS debe evitar ciclos y regresar tan pronto como detecte uno.