Business
Jobs
  • About Us
  • Solutions
    • Job Postings
      Post your job and receive qualified candidates in 48h.
    • Candidate Assessments
      500+ technical and psychological tests, plus anti-fraud.
    • Headhunting
      Tailor-made executive search from start to finish.
    • Payroll + EOR
      Payroll dispersal and EOR across 15+ LATAM countries.
  • Pricing
  • Jobs

0

142
Views
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 answers
Answer question

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 Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Sales
Legal
Terms and conditions Privacy policy
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Show me some job opportunities
There's an error!