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
Consider a simple graph with two nodes:
There are two edges as well:
In your DFS approach, you have following steps
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.