Day 9 — Graphs (Basics)
A graph is the most general data structure in our toolbox. Linked lists, trees, grids — they’re all graphs with extra rules. So is the road network you used to get here, the social network you scroll on, the dependency graph npm grumbles about, and the citation network of every research paper ever written.
Today is foundation day. We won’t solve a hundred problems — we’ll learn the vocabulary and the two representations that 95% of graph code uses. That’s enough to unlock the rest of the course.
What you’ll learn today
- What a graph actually is — vertices and edges, and the four big design choices (directed vs undirected, weighted vs unweighted)
- The vocabulary: degree, path, cycle, connected component, DAG, bipartite
- The two universal representations: adjacency list and adjacency matrix — when each wins
- Special graph shapes you’ll meet again: trees, DAGs, bipartite graphs
- Where graphs power real systems — social networks, recommendations, package managers, navigation, biology
- Warm-up exercises that drill graph modeling and the basic invariants
- Six practice problems that exercise the graph model without any traversal yet — you’ll start traversing on Day 10
Why graphs are the master template
A huge fraction of “real algorithm problems” are graph problems in disguise. Once you can spot the graph hiding inside a problem statement, the rest is choosing the right traversal.
- Social network — “people who liked the same posts” → bipartite graph between people and posts.
- Word ladder — words become nodes, edges connect words that differ by one letter. Shortest path = BFS.
- Course prerequisites — courses are nodes, “must finish A before B” is a directed edge. “Can I graduate?” = topological sort.
- Pathfinding in a maze — every cell is a node, neighbours are edges. BFS or A*.
- State machines — states are nodes, transitions are edges. “Can I reach state X from state A?” = reachability.
You’ll meet all of these (and many more) in later chapters. Today we lay the groundwork.
Day 6 already taught you about trees — and a tree is just a special kind of graph: connected, undirected, no cycles. Most tree algorithms generalize naturally to graphs once you add a “visited” set to prevent re-visiting. We’ll see exactly that on Day 10 — DFS & BFS.
Roadmap
- Introduction — definitions, terminology, the four design choices that shape every graph.
- Representing Graphs — adjacency list vs adjacency matrix, the code in C++/Python/Java, and when each wins.
- Types of Graphs — DAGs, trees, bipartite graphs, complete graphs, weighted graphs, and what each one is good for.
- Applications — where graphs actually earn their keep: social networks, package managers, recommendation systems, navigation, biology, distributed systems.
- Basic Questions — warm-up exercises: count edges from a degree sequence, model a problem as a graph, hand-build adjacency lists.
- Practice Questions — six model-only problems to lock in the representation before we start traversing on Day 10.
Coming up next on Day 10 — the two universal graph algorithms: DFS and BFS. Once you have both, you’ve unlocked the door to shortest paths, cycle detection, connected components, topological sort, and most of the graph practice problems on the internet.