Run BFS and record parents as you go:
// During BFS, when visiting v from u:
parent[v] = u
// After BFS, reconstruct path from s to t:
path = []
current = t
while current != 0:
path.append(current)
current = parent[current]
path.reverse()
When you process node and visit neighbor , set parent[v] = u before adding to the queue. After BFS completes, start at and backtrack through parents until you reach . Reverse to get the path from to .
If you never reached during BFS, parent[t] is still , meaning no path exists.
This runs in time and uses space.