Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

145
Visualizações
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 Respostas
Responde à pergunta

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 Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda