Graph Algorithms
Graph Algorithms
A graph is the most general data structure you have: a set of vertices (nodes) connected by edges (relationships). Trees, linked lists, grids, and state machines are all just special-case graphs. The moment a problem says "network", "dependency", "route", "connection", "reachability", or "can I get from A to B", you are looking at a graph problem. The whole field of graph algorithms is really the study of two questions: how do I systematically visit everything reachable, and how do I find the best (usually shortest or cheapest) way through.
The intuition that unlocks the field: nearly every graph algorithm is a disciplined way of exploring outward from a starting point, deciding what to visit next. Change that one decision rule and you get a completely different algorithm.
Precise definitions and representation
A graph G = (V, E) has vertex set V (size n) and edge set E (size m). Edges may be directed (A→B only) or undirected (A—B both ways), and weighted (each edge carries a cost) or unweighted. Two standard representations:
- Adjacency list: for each vertex, a list of its neighbours. Space
O(n + m). Iterating a vertex's neighbours isO(deg). This is the default for the sparse graphs (m ≪ n2) that dominate interviews and real systems. - Adjacency matrix: an
n × ntable where cell[u][v]holds the edge weight (or 0/∞). SpaceO(n2). Edge lookup isO(1), but listing neighbours costsO(n). Preferred only for dense graphs or algorithms that probe arbitrary pairs.
The two workhorse traversals both run in O(n + m) on an adjacency list — you touch every vertex once and every edge at most twice. They differ only in the data structure holding the frontier:
- BFS (breadth-first) uses a FIFO queue: explore layer by layer. On an unweighted graph it finds shortest paths in edges.
- DFS (depth-first) uses a stack (often recursion): dive deep before backtracking. Powers cycle detection, topological sort, and connected-component labelling.
Worked example: Dijkstra, counted step by step
For a weighted graph with non-negative weights, shortest paths come from Dijkstra's algorithm: repeatedly pull the closest unfinalised vertex from a min-heap, then relax its outgoing edges (update a neighbour if going through this vertex is cheaper). Once a vertex is popped, its distance is final. Let's find shortest distances from S on this graph, matching the diagram below. Edges: S→A(4), S→B(1), B→A(2), B→C(5), A→C(3), A→D(6), C→D(1).
- Init
dist = {S:0, rest:∞}. Heap:[(0,S)]. - Pop S (0). Relax S→A: 0+4=4 < ∞ → A=4. S→B: 0+1=1 → B=1. Heap:
[(1,B),(4,A)]. - Pop B (1). Relax B→A: 1+2=3 < 4 → A improves to 3. B→C: 1+5=6 → C=6. Heap:
[(3,A),(4,A stale),(6,C)]. - Pop A (3). Relax A→C: 3+3=6, not < 6, skip. A→D: 3+6=9 → D=9. Heap:
[(4,A stale),(6,C),(9,D)]. - Pop A (4) — stale (already finalised at 3). Discard in O(1) and continue. This lazy-deletion is why the heap can briefly hold duplicates.
- Pop C (6). Relax C→D: 6+1=7 < 9 → D improves to 7. Heap:
[(7,D),(9,D stale)]. - Pop D (7). Done. Final:
S=0, B=1, A=3, C=6, D=7.
Note the greedy choice paid off: taking S→B→A→...→C→D (cost 7) beat the tempting direct S→A→D (cost 10). Complexity with a binary heap: O((n + m) log n) — each of m edges can trigger one push, and each pop costs log n.
Common pitfalls and what an interviewer probes
- Using Dijkstra with negative edges. The "once popped, it's final" invariant breaks — a cheaper path could arrive later through a negative edge. Interviewers love this. The fix is Bellman-Ford (
O(n·m)), which relaxes all edgesn−1times and can also detect negative cycles (a further relaxation still improves something). - BFS on a weighted graph. Plain BFS counts edges, not weight, so it gives wrong answers when weights differ. Only valid when all weights are equal (or 1).
- Forgetting the visited set. Without marking nodes, cyclic graphs loop forever. Mark on enqueue (BFS) to avoid duplicate frontier entries.
- Directed vs undirected confusion, and mishandling disconnected graphs — a single traversal only covers one component, so loop over all start vertices when you need everything.
- "Which algorithm?" The expected reflex: unweighted shortest path → BFS; non-negative weights → Dijkstra; negative weights → Bellman-Ford; all-pairs on a small dense graph → Floyd-Warshall (
O(n3)); ordering under dependencies → topological sort; minimum-cost connecting tree → Kruskal/Prim (MST).
Where it matters + trade-offs
Graph algorithms are the backbone of real systems: routing protocols (OSPF runs Dijkstra), Google Maps and GPS (Dijkstra/A* with heuristics), build systems and package managers (topological sort over dependency DAGs — a cycle means an impossible build), social-network friend suggestions and web crawling (BFS/DFS), network provisioning and clustering (MST), and deadlock detection (cycle finding in a resource graph).
The complexity trade-off is a ladder you climb only as far as the graph demands. BFS/DFS at O(n+m) are as cheap as reading the graph — always your first tool. Dijkstra's O((n+m) log n) adds a log factor to buy weighted correctness. Bellman-Ford's O(n·m) is markedly slower but the price of surviving negative weights. Floyd-Warshall's O(n3) only wins when you truly need all pairs on a small graph. The discipline that separates strong candidates: reach for the cheapest algorithm whose assumptions your graph actually satisfies — never pay for generality you don't need, and never assume properties (non-negativity, acyclicity) the input hasn't guaranteed.
Key takeaways
- A graph is
(V, E); store sparse graphs as adjacency lists (O(n+m)space) and reach for a matrix only when dense or doingO(1)pair lookups. - Every traversal is "explore outward, decide what's next": a queue gives BFS (unweighted shortest paths), a stack gives DFS (cycles, topo-sort, components) — both
O(n+m). - Match the shortest-path tool to the weights: BFS (unweighted) → Dijkstra
O((n+m)log n)(non-negative) → Bellman-FordO(n·m)(negative, detects negative cycles) → Floyd-WarshallO(n3)(all-pairs, small). - Interview reflexes: never run Dijkstra on negative edges, always keep a visited set, distinguish directed/undirected, and handle disconnected components explicitly.
🤖 Don't fully get this? Learn it with Claude
Stuck on Graph Algorithms? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Graph Algorithms** (DSA) and want to truly understand it. Explain Graph Algorithms from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Graph Algorithms** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Graph Algorithms** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Graph Algorithms** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.