Graph Algorithms for Interviews

Representing a Graph

• Adjacency list: List of neighbors per node. Best for sparse graphs and traversal.
• Adjacency matrix: matrix[i][j] = weight or 1/0. Best for dense graphs or O(1) edge lookup.

BFS (Breadth-First Search)

Use a queue. Explores level by level.

When to use: Shortest path in unweighted graphs, level-order, connected components.

Interview favorites: Number of islands, word ladder, clone graph.

DFS (Depth-First Search)

Use recursion or a stack. Explores as deep as possible first.

When to use: Cycle detection, topological sort, path finding, connected components.

Interview favorites: Clone graph, number of islands, course schedule.

Topological Sort

Ordering of nodes in a DAG. Kahn's algorithm (BFS): in-degrees and queue. DFS: push after visiting descendants, then reverse.

When to use: Course schedule, task scheduling, dependency order.

Dijkstra's Algorithm

Shortest path from one source with non-negative edge weights. Use a min-heap keyed by distance.

When to use: Weighted shortest path, network delay time.

Quick Reference

Goal	Algorithm	Notes
Shortest path (unweighted)	BFS	Level = distance
Shortest path (non-negative)	Dijkstra	Min-heap
Cycle detection	DFS	Gray/black
Dependency order	Topo sort	Kahn or DFS

Master these and you'll be ready for most graph interview questions. Practice with Preplume(/) timelines.