roadmap/Graphs (DFS / BFS)

Topic 10 / 16

Graphs (DFS / BFS)

HardNon-Linear~7 days
Challenging
progress0 / 15 solved

Model relationships. DFS for exploration; BFS for shortest unweighted paths.

⚠️
Why this topic is hard

Graphs are hard because there's no standard structure like a tree — a graph can have cycles, disconnected components, and multiple valid representations (adjacency list vs matrix). The hardest part is recognizing WHICH graph algorithm applies: cycle detection? Topological sort? Shortest path? Each requires a different approach.

Concept

Graphs model pairwise relationships between entities (nodes/edges). DFS explores as deep as possible before backtracking — good for connected components, cycle detection, and topological sort. BFS explores level by level using a queue — guarantees shortest path in unweighted graphs.

When to use this pattern
  • ◆Connectivity, reachability, or island counting
  • ◆Shortest path in unweighted graph → BFS
  • ◆Topological ordering (courses, dependencies)
  • ◆Grid problems: 4-directional flood fill
  • ◆Bipartite check, cycle detection
Common patterns
DFS — iterative/recursive
Use visited set. Recurse into unvisited neighbors.
BFS — shortest path
Queue + visited set. Level-by-level expansion.
Topological sort (Kahn's)
Track in-degree. Start from 0-in-degree nodes; BFS.
Union-Find
Efficiently merge components and check connectivity.
Visual walkthrough
Graphs
BFS vs DFS Exploration
BFS uses a queue → explores level by level → guarantees shortest path in unweighted graphs.
start node:
0d=01234567
current
visited
in queue
queue:0
Start BFS from node 0. Add to queue.
BFS explores all neighbors at distance 1, then distance 2, etc.
step 1/30
Brute force → optimal thinking
Brute force
Try all paths with no cycle detection → infinite loop on cyclic graphs.
Observation
Each node need only be visited once. A visited set prevents revisiting.
Optimization
DFS with visited: O(V+E). For shortest path, BFS guarantees minimum hops level by level.
Final complexity
O(V + E) for both DFS and BFS on adjacency list representation.
Quick Recall Check

Which algorithm finds the shortest path in an unweighted graph?

How do you detect a cycle in a directed graph using DFS?

In multi-source BFS (e.g. Rotting Oranges), how do you initialise the queue?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Backtracking
next
Dynamic Programming
→
Progress is saved on this device