Empresas
Empleos
  • Sobre nosotros
  • Soluciones
    • Publicación de vacantes
      Publica tu vacante y recibe candidatos calificados en 48h.
    • Evaluación de candidatos
      500+ pruebas técnicas y psicológicas, más anti-fraude.
    • Headhunting
      Búsqueda ejecutiva a la medida de principio a fin.
    • Nómina + EOR
      Dispersión de nómina y EOR en más de 15 países de LATAM.
  • Precios
  • Empleos

0

146
Vistas
Graph Traversal (is there a connection between source and destination nodes in the graph) - visited DFS vs BFS

I don't understand for potential cyclic graph traversals, why for is there a connection between source and destination node in the graph:

i) DFS, if a node is visited, we return false

ii) BFS, if a node is visited, we continue (in the loop)

example code (from 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'); // -> true
about 4 years ago · Santiago Trujillo
1 Respuestas
Responde la pregunta

0

Consider a simple graph with two nodes:

  • A (the start)
  • B (the target)

There are two edges as well:

  • A->A
  • A->B

In your DFS approach, you have following steps

  • pop a current node off the stack, which gives you A
  • it's not the destination and wasn't visited, so you add it to the list of visited nodes
  • you now add the neighbours to the stack, which are A and B
  • next iteration, you pop another current node off the stack, which gives you A again
  • it was already visited, so you return false, even though a path exists

In short, your algorithm is faulty. Note that this doesn't even require the special case of an edge looping in on itself. All it takes is a loop that is evaluated before reaching the target. Also, if by chance the neighbor B was checked first, you would have gotten a correct result.

about 4 years ago · Santiago Trujillo Denunciar
Responde la pregunta
Encuentra empleos remotos

¡Descubre la nueva forma de encontrar empleo!

Top de empleos
Top categorías de empleo
Empresas
Publicar vacante Precios Comercial
Legal
Términos y condiciones Política de privacidad
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomiéndame algunas ofertas
Necesito ayuda