Has Path (Graph Reachability)
A reachability check is just DFS that stops the instant it sees the target — the only real addition over plain traversal is a `visited` set, which now earns its keep because this graph has a genuine cycle (`g` and `i` point at each other).
The problem
Implement `hasPath(graph, source, target)` returning whether `target` is reachable from `source` in a directed adjacency-list graph.
The sample graph has a cycle: `i: ['g', 'k']` and, transitively via `g -> h`, no way back to `i` — but other nodes do cycle back, e.g. two different nodes (`i` and `j`) both point at `g`. Walking it without tracking visited nodes would loop forever on any graph where two nodes point at each other.
The approach
Same iterative stack-based skeleton as plain DFS, plus two changes: a `visited` `Set` seeded with `source`, and an early return the moment a neighbour equals `target` — no need to finish the traversal once the answer is known.
`source == target` is checked upfront as its own base case, since the main loop only ever inspects *neighbours* for a target match, never the popped node itself — without that check, asking `hasPath(graph, 'a', 'a')` would incorrectly search neighbours instead of immediately returning `true`.
Marking a node `visited` at push time (not at pop time) is what keeps the cycle from causing repeat work: `i` and `g` reference each other, so without marking `g` visited the moment it's queued, it could be pushed again from a different path and re-explored.
The solution
export function hasPath(graph, source, target) {
if (source == target) return true
const visited = new Set()
visited.add(source)
const stack = [source]
while (stack.length) {
const node = stack.pop()
for (let neighbour of graph[node]) {
if (!visited.has(neighbour)) {
if (neighbour == target) {
return true
}
visited.add(neighbour)
stack.push(neighbour)
}
}
}
return false
}Time O(V + E)Space O(V)