Chapter 18 — Graphs: BFS & DFS
Chapter 18 — Graphs: BFS & DFS
Hey everyone! Welcome back to Namaste DSA!
A graph is the most general data structure of all — just dots (nodes) connected by lines (edges). Social networks, maps, the internet, dependencies — all graphs. The two traversals you must know cold are BFS and DFS. Master them and you can solve shortest paths, connectivity, and cycle detection.
What we will cover:
- Graph vocabulary & types
- Adjacency list vs adjacency matrix
- BFS — explore level by level (queue)
- DFS — go deep first (recursion/stack)
- The visited set — avoiding infinite loops
- Connected components
- Shortest path (unweighted) & cycle detection
- Interview Questions
1. Graph Vocabulary
┌─────────────────────────────────────────────────────────────┐ │ NODES (vertices) connected by EDGES │ ├─────────────────────────────────────────────────────────────┤ │ (A)────(B) │ │ │ / │ │ │ │ / │ • Directed: edges have arrows │ │ (C)────(D) (one-way, like Twitter follow)│ │ • Undirected: two-way │ │ (friendship) │ │ • Weighted: edges have costs │ │ • Cyclic: contains a loop │ └─────────────────────────────────────────────────────────────┘
2. Adjacency List vs Adjacency Matrix
| Adjacency List | Adjacency Matrix | |
|---|---|---|
| Stores | Each node → list of neighbors | n×n grid, 1 = edge |
| Space | O(V + E) | O(V²) |
| Check edge (u,v)? | O(degree) | O(1) |
| Best for | Sparse graphs (most graphs!) | Dense graphs |
// Adjacency list — the usual choice
const graph = {
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "D"],
D: ["B", "C"]
};
3. BFS — Breadth-First Search (Level by Level)
Explore all neighbors first, then their neighbors. Uses a queue. BFS finds the shortest path in an unweighted graph because it reaches nodes in order of distance.
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
const order = [];
while (queue.length) {
const node = queue.shift(); // front
order.push(node);
for (const next of graph[node]) {
if (!visited.has(next)) {
visited.add(next); // mark BEFORE enqueue
queue.push(next);
}
}
}
return order;
}
HAND TRACE: bfs(graph, "A")
queue=[A] visited={A}
pop A → neighbors B,C → queue=[B,C] visited={A,B,C}
pop B → neighbor D → queue=[C,D] visited={A,B,C,D}
pop C → D visited → queue=[D]
pop D → all visited → queue=[]
order = [A, B, C, D] ✔
4. DFS — Depth-First Search (Go Deep First)
Follow one path as far as possible, then backtrack. Uses recursion (the call stack) or an explicit stack.
function dfs(graph, node, visited = new Set(), order = []) {
visited.add(node);
order.push(node);
for (const next of graph[node]) {
if (!visited.has(next)) {
dfs(graph, next, visited, order); // recurse deeper
}
}
return order;
}
BFS vs DFS on the same graph: BFS from A → A, B, C, D (closest first) DFS from A → A, B, D, C (deepest first)
5. The Visited Set — Critical!
┌─────────────────────────────────────────────────────────────┐ │ WITHOUT a visited set, a cyclic graph loops FOREVER! │ │ │ │ A → B → A → B → A → ... (infinite) │ │ │ │ Always mark a node visited when you discover it. │ │ (For BFS, mark on ENQUEUE — not dequeue — to avoid │ │ adding the same node to the queue twice.) │ └─────────────────────────────────────────────────────────────┘
6. Connected Components
Count separate "islands" of connected nodes by running DFS/BFS from every unvisited node.
function countComponents(graph, nodes) {
const visited = new Set();
let count = 0;
for (const node of nodes) {
if (!visited.has(node)) {
count++; // new island!
dfs(graph, node, visited); // flood the whole component
}
}
return count;
}
7. Shortest Path & Cycle Detection
SHORTEST PATH (unweighted) → BFS, tracking distance per level.
(Weighted graphs need Dijkstra — a heap-based BFS, Chapter 16's heap.)
CYCLE DETECTION:
• Undirected: during DFS, if you reach a visited node that
isn't the one you came from → cycle.
• Directed: track nodes in the CURRENT recursion path; if you
revisit one still "in progress" → cycle (used in topological sort).
| Traversal | Data structure | Finds | Time |
|---|---|---|---|
| BFS | Queue | Shortest path (unweighted) | O(V + E) |
| DFS | Stack / recursion | Connectivity, cycles, topo sort | O(V + E) |
Interview Questions — Quick Fire!
Q: Adjacency list vs adjacency matrix — when to use each?
"An adjacency list uses O(V + E) space and is best for sparse graphs, which most real graphs are. A matrix uses O(V²) space but checks whether a specific edge exists in O(1), so it's better for dense graphs or when you query edges constantly."
Q: What's the difference between BFS and DFS?
"BFS explores level by level using a queue and finds the shortest path in unweighted graphs. DFS goes as deep as possible along one path before backtracking, using recursion or a stack, and is natural for connectivity, cycle detection, and topological sorting. Both are O(V + E)."
Q: Why do you need a visited set?
"To avoid revisiting nodes and looping forever in cyclic graphs, and to avoid redundant work. In BFS you should mark a node visited when you enqueue it, not when you dequeue it, otherwise the same node can be added to the queue multiple times."
Q: How does BFS give the shortest path in an unweighted graph?
"BFS visits nodes in increasing order of distance from the source — all nodes one edge away, then two edges away, and so on. So the first time you reach a node is via the fewest edges, which is the shortest path. For weighted edges you'd use Dijkstra instead."
Q: How do you count connected components?
"Iterate over all nodes; whenever you find an unvisited one, increment a counter and run DFS or BFS to mark its entire component visited. Each new traversal start corresponds to one separate component."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Graph | Nodes + edges; directed/weighted/cyclic. |
| Adjacency list | O(V+E) space — default choice. |
| BFS | Queue, level by level, shortest path. |
| DFS | Stack/recursion, deep first, cycles & components. |
| Visited set | Prevents infinite loops. |
| Both | O(V + E). |
What's Next?
That completes Season 4! Next is the final stretch — Season 5: Advanced Algorithms, starting with Chapter 19: Backtracking, the "try everything, undo, try again" technique behind subsets, permutations, and N-Queens.
Keep coding, keep grinding! See you in the next one!
Post a Comment