Given a directed acyclic graph as an adjacency list, return true if there is a
path from src to dst following edge directions.
hasPath(graph, src, dst)
Input format: edges | src | dst. Edges are a,b pairs meaning a directed edge
a → b. For example f,g f,i g,h i,g i,k | f | k.
edges f,g f,i g,h i,g i,k, src f, dst k // → true (f → i → k)
edges f,g f,i g,h i,g i,k, src f, dst h // → true (f → g → h)
edges f,g f,i g,h i,g i,k, src g, dst f // → false (edges are directed)
The input describes directed connections — "a leads to b" — naturally represented as a graph where each node's adjacency list holds what it can directly step to. "Can I get from src to dst" really asks: starting at src, moving only along the arrows, can I ever land on dst?
Start with the smallest version: if src and dst are the same node, the answer is trivially yes — zero steps needed. That's the base case.
Otherwise: can I reach dst from any of src's direct neighbours? If yes for even one, then src can reach dst too — take one step there, then follow whatever path it uses. "Can src reach dst" reduces to "can any of src's neighbours reach dst" — the same question, asked from a different starting point. Keep shrinking it, one hop at a time, until you land on dst or run out of neighbours.
"Try each neighbour, and for each one, try each of its neighbours" is exactly depth-first search: dive as deep as possible down one path before backing up to try another. You don't need distances or a particular exploration order — just whether any path exists — so exhausting one direction before the next is fine.
Since this graph is guaranteed acyclic, the recursion can't loop back on itself — every call moves further along a chain that can't circle back. That's why a plain recursive DFS terminates safely with no visited set. This is a special case, though: the moment a directed graph can have cycles, the same approach would spin forever, and you'd need a visited set, exactly as later problems require. Recognizing when a graph is guaranteed acyclic versus when it might cycle is a judgment call you'll make repeatedly.
def has_path(graph, src, dst):
if src == dst:
return True
for nxt in graph.get(src, []):
if has_path(graph, nxt, dst):
return True
return False
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.