Pattern #17 — Graphs 🕸️

Pattern #17 — Graphs 🕸️

Graphs sound scary but they're everywhere in real life: friends on social media, cities connected by roads, web pages linked together. A graph is just things (nodes) connected by relationships (edges).

1. The Idea (in one line)

A graph is a set of NODES (dots) connected by EDGES (lines).

   Real-life analogy 👥
   ────────────────────
   Facebook friends. Each PERSON is a node. Each FRIENDSHIP is
   an edge connecting two nodes. "Are these two people connected
   through friends-of-friends?" is a graph question.

2. The Picture & Vocabulary

       A ─────── B
       │         │
       │         │
       C ─────── D ─────── E

   NODE (vertex): A, B, C, D, E  (the dots)
   EDGE: the lines (A-B, A-C, B-D, C-D, D-E)

   DIRECTED vs UNDIRECTED:
   • Undirected: friendship (if A knows B, B knows A) — lines
   • Directed:   Twitter follow (A→B doesn't mean B→A) — arrows

   WEIGHTED vs UNWEIGHTED:
   • Weighted: roads with distances (A—5—B)
   • Unweighted: just connected or not

3. How to STORE a Graph (this is the key skill)

   ADJACENCY LIST (the one you'll use 95% of the time) 🎯
   ──────────────────────────────────────────────────────
   For each node, keep a list of its neighbours:

   A: [B, C]
   B: [A, D]
   C: [A, D]
   D: [B, C, E]
   E: [D]

   In code (a Map or object):
   const graph = {
     A: ['B', 'C'],
     B: ['A', 'D'],
     ...
   };

   ✅ Space-efficient, easy to loop a node's neighbours.

   (There's also an "adjacency matrix" — a 2D grid of true/false —
    but the list is usually simpler and lighter.)

4. Building a Graph from an Edge List

   Most problems GIVE you edges like [[A,B],[A,C],[B,D]].
   You BUILD the adjacency list first:

   function buildGraph(edges) {
     const graph = {};
     for (const [a, b] of edges) {
       (graph[a] ??= []).push(b);
       (graph[b] ??= []).push(a);   // both ways = UNDIRECTED
       // for a DIRECTED graph, only add graph[a].push(b)
     }
     return graph;
   }

5. 🔍 How to SPOT This Pattern

   Use Graph thinking when you see:
   ✅ "nodes and edges", "connected", "network"
   ✅ "friends", "cities/roads", "web of ..."
   ✅ "can you get from X to Y?"
   ✅ "number of connected groups / components"
   ✅ A GRID is secretly a graph (each cell connects to neighbours)!

6. What Do You DO With a Graph?

   Almost everything is one of these two traversals:

   • DFS (Depth-First Search) → Pattern #18
     Go as DEEP as possible down one path, then back up.

   • BFS (Breadth-First Search) → Pattern #19
     Explore LEVEL by level, nearest first.

   These two unlock: "is it connected?", "shortest path",
   "count components", "detect a cycle", and more.

7. Practice Problems

   ⭐ core (get comfy building & traversing)
   • Find if Path Exists in Graph
   • Number of Connected Components
   • Clone Graph

   ⭐⭐ Medium
   • Number of Islands (grid graph)
   • Course Schedule (directed graph + topo sort)
   • Rotting Oranges (grid + BFS)
   • Word Ladder

8. ⚠️ Common Mistake

   ❌ Forgetting to add edges BOTH ways for an undirected graph.
   ❌ Not tracking VISITED nodes → infinite loops when the graph
      has cycles. Always keep a `visited` set during traversal.

Key Takeaway

   Graph = nodes + edges. Store it as an adjacency list (each node
   → its neighbours). Directed vs undirected and weighted vs not
   are the key properties. You explore graphs with DFS and BFS —
   the next two patterns. Even grids are graphs.

Next: Pattern #18 — DFS, going deep. 🏊