Given an undirected graph as an adjacency list, return true if there is a path
between src and dst. Because undirected graphs contain cycles, you must track
visited nodes to avoid looping forever.
undirectedPath(graph, src, dst)
Input format: edges | src | dst. Edges are a,b pairs, each connecting both
ways.
edges i,j k,i m,k k,l o,n, src i, dst m // → true (i – k – m)
edges i,j k,i m,k k,l o,n, src i, dst o // → false (different component)
At first glance this looks identical to searching for a path in a directed graph: start at src, try each neighbour, see if you can reach dst. But this graph is undirected — every edge goes both ways. If a connects to b, then a shows up in b's neighbour list and b shows up in a's. That opens the door to cycles: from a you can go to b, from b back to a, from a to b again, forever.
Reusing "try every neighbour recursively" with no memory of where you've been, the search can bounce across a cycle indefinitely, never terminating. The new idea: whenever a graph might contain cycles, you must track which nodes you've already visited during this search, and refuse to revisit them.
Each node gets added to the visited set at most once and is never explored again from this search. Since the graph has finitely many nodes, the search must eventually run out of new nodes and terminate — no infinite loop, regardless of how many cycles exist.
If the search exhausts everything reachable from src without landing on dst, dst is unreachable — a different, disconnected part of the graph. This "mark visited before recursing, skip anything already visited" pattern is the foundation for essentially every other undirected graph problem: counting components, measuring component sizes, finding shortest paths.
def undirected_path(graph, src, dst):
visited = set()
def dfs(node):
if node == dst:
return True
if node in visited:
return False
visited.add(node)
for nxt in graph.get(node, []):
if dfs(nxt):
return True
return False
return dfs(src)
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.