BFS Shortest Path

Your Task

Write a function bfs_shortest_path(graph, start, target) that finds the shortest path (fewest edges) between start and target in an unweighted, undirected graph.

Return the path as a list of nodes from start to target. If no path exists, return None.

The graph is given as an adjacency list where graph[node] is a list of neighbors.

---

Example

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(bfs_shortest_path(graph, "A", "F"))
# ["A", "C", "F"]  — 2 hops

print(bfs_shortest_path(graph, "A", "E"))
# ["A", "B", "E"]  — 2 hops

print(bfs_shortest_path(graph, "D", "F"))
# ["D", "B", "E", "F"]  — 3 hops

Why BFS? BFS explores nodes level by level (1 hop away, then 2 hops, then 3...), so the first time it reaches the target it has taken the fewest hops possible.

---

Expected Complexity

	Complexity
Time	O(V + E)
Space	O(V)

Where V is the number of nodes and E is the number of edges.

---

Approach

1. Use a queue (deque) and a visited set — same as regular BFS
2. But instead of storing just nodes, store the entire path so far in the queue
3. When you reach the target, return that path immediately — it's the shortest one
4. If the queue empties without finding the target, return None

Key insight: Unlike Dijkstra, BFS doesn't need edge weights or a priority queue. All edges cost the same (1 hop), so the first path found is always shortest.

---

Starter Code

from collections import deque

def bfs_shortest_path(graph, start, target):
    # Your code here
    pass


# Test your function:
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(bfs_shortest_path(graph, "A", "F"))
# Expected: ["A", "C", "F"]

print(bfs_shortest_path(graph, "A", "E"))
# Expected: ["A", "B", "E"]

print(bfs_shortest_path(graph, "D", "F"))
# Expected: ["D", "B", "E", "F"]  or  ["D", "B", "A", "C", "F"] (same length)

print(bfs_shortest_path(graph, "A", "A"))
# Expected: ["A"]

print(bfs_shortest_path(graph, "A", "Z"))
# Expected: None

---

Hints