Why graphs matter
Placement graph questions often hide inside simple stories: cities and roads, friends, courses, islands, servers, or college clubs.
Your job is usually not to invent a complex algorithm. First build the graph. Then traverse it safely.
One idea
Graph traversal is controlled exploration. Keep a visited set, then use a queue for BFS or a stack/recursion for DFS.
BFS is best when you need the minimum number of edges in an unweighted graph. DFS is handy for components, cycles, and reachability.
Build the graph
Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.
0 of 5 done
BFS shortest path
This is the pattern for minimum buses, minimum roads, or minimum friend links when every edge has equal cost.
Save this as graphs/bfs_shortest_path.py in your repo.
from collections import deque
def shortest_path(n, edges, start, target):
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a) # remove this line for a directed graph
dist = [-1] * n
dist[start] = 0
q = deque([start])
while q:
node = q.popleft()
if node == target:
return dist[node]
for nei in graph[node]:
if dist[nei] == -1:
dist[nei] = dist[node] + 1
q.append(nei)
return -1
if __name__ == "__main__":
n = 6
edges = [(0, 1), (0, 2), (1, 3), (2, 4), (4, 5)]
print(shortest_path(n, edges, 0, 5)) # 3Use AI carefully
You can ask ChatGPT or Gemini: “Give me 5 placement-style graph traversal problems using BFS and DFS, with sample inputs.”
Check the output. Make sure edges, indexing, directed versus undirected, and expected answers are consistent before adding anything to your repo.
Common bug
Do not mark a node visited only when you pop it from the queue. In BFS, mark it when you push it.
If you mark late, the same node can enter the queue many times. That can slow down your code and confuse distance updates.
README note
For every graph solution, write what the nodes and edges mean. A recruiter should not guess your model.
Add a small complexity note beside the code file.
### Graph traversal: shortest path in unweighted graph
File: graphs/bfs_shortest_path.py
Approach:
- Build an adjacency list from the edge list.
- Run BFS from the start node.
- Store distance in edges from the start.
- Return -1 if the target is not reachable.
Complexity:
- Time: O(V + E), because each node and edge is processed at most once.
- Space: O(V + E), for the graph, queue, and distance array.Do this now
Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.
0 of 5 done