Remember the way you came
Keep the trail you are on as a list, adding a node as you enter it and removing it when you back out. About 15 minutes.
A list that shows the way
Saying "yes, you can get there" is useful, but a map app gives you the actual route. To get one, keep a list of the places on your current trail. Each time you step into a new place, add it to the end. If that place turns out to be a dead end, take it off again before trying another door.
It is the same choose, explore, undo rhythm you met in backtracking. When you reach the target, the list already holds the route from the start.
Same doors, same route
Different graphs can have several routes to the same place, and a depth-first search finds whichever it tries first. To make the answer the same every time, agree on an order: here, look at a place's neighbours from the smallest number to the largest.
With that rule the route is fixed. If the target cannot be reached, the trail is emptied as the search backs out, and you return an empty list.
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
path, seen = [], [False] * n
def visit(node):
seen[node] = True
path.append(node)
if node == target:
return True
for nxt in sorted(adj[node]):
if not seen[nxt] and visit(nxt):
return True
path.pop()
return False
return path if visit(start) else []- trail
- [0]
Start at 0. The trail so far is just 0.
The trail is [0, 1, 3, 4] and node 4 is a dead end. What is the trail after backing out of 4?
- A[0, 1, 3]
- B[0]
- C[0, 1, 3, 4]
Show the answer
[0, 1, 3]. Only the dead-end node is removed. The search is now standing on 3, ready to try its next neighbour.
The way there
There are n places, numbered 0 to n − 1, joined by two-way roads. edges[i] = [a, b] means a road between place a and place b. Do a depth-first search from start, visiting each place's neighbours from the smallest number to the largest. Return the list of places on the route from start to target that this search finds first, including both ends, or an empty list if target cannot be reached.
n = 6, edges = [[0, 1], [0, 2], [1, 3], [3, 4], [2, 5]], start = 0, target = 5 → [0, 2, 5]
1 ≤ n ≤ 500 · 0 ≤ roads ≤ 5,000 · no road joins a place to itself