Look at a Delhi Metro map. Stations, and lines connecting them. Rajiv Chowk touches six other stations; some quiet station touches two. Now try to store that map in a tree. Which station is the root? Nobody is anyone's "parent". And the Ring Line goes around in a circle — trees forbid cycles outright.
The metro map needs a looser structure: just things and connections, with no further promises. That structure is the graph — and so are your UPI contacts, Instagram follows, flight routes, course prerequisites, and the web itself. This lesson is about modelling and STORING graphs well; the algorithms that walk them get their own lessons in the Algorithms course.
The words: vertices, edges, paths, cycles
- Vertex (or node) — a thing: a station, a person, a webpage. Count: V.
- Edge — a connection between two vertices. Count: E.
- Neighbours — vertices sharing an edge.
- Path — a sequence of edges from one vertex to another; its length is the number of edges.
- Cycle — a path that returns to its start (the Ring Line).
- Connected — every vertex reachable from every other; otherwise the graph splits into connected components (islands).
Two modelling questions before any code
Before storing anything, answer two questions about your relationship — real bugs live here, not in the code:
Question 1 — is the connection one-way or mutual? WhatsApp contacts: mutual → undirected edges. Instagram follows: A following B does NOT make B follow A → directed edges (arrows). Course prerequisites, web links, money owed — all arrows. Model a one-way relation as undirected and you have silently invented connections that don't exist; your code will "work" and answer wrongly.
Question 2 — do connections have a cost? Metro stations with kilometres between them → weighted. Just "connected or not" → unweighted. This single bit later decides your shortest-path algorithm: BFS for unweighted, Dijkstra for weighted.
Storing a graph: two candidates
What would we naturally do? Perhaps a big table: one row and one column per vertex, a 1 where an edge exists. That's a real design — the adjacency matrix: V × V cells, matrix[u][v] = 1 (or the weight) if u connects to v.
The alternative: store, for each vertex, just the list of its neighbours — the adjacency list, a dict from vertex to neighbours. Only the edges that exist take space.
List vs matrix: the honest cost battle
Pause and estimate: 10,000 users, 30,000 friendships. How many cells does the matrix need?
10,000² = 10 crore cells — to record 30,000 connections. 99.97% zeroes. The list stores ~V + 2E ≈ 70,000 entries. And this isn't a cooked example: real graphs are almost always sparse — crores of users, but each follows a few hundred people, not crores. That's why the list is the default. The matrix keeps exactly one superpower: answering "is there an edge u–v?" in O(1), one cell read.
| Operation | Adjacency list | Adjacency matrix |
|---|---|---|
| Memory | O(V + E) | O(V²) |
| Edge u–v exists? | O(degree(u)) — scan u's list | O(1) |
| All neighbours of u | O(degree(u)) — exactly them | O(V) — scan the whole row |
| Add an edge | O(1) | O(1) |
| Best when | sparse; traversal-heavy | dense; edge-lookup-heavy |
The one-sentence verdict for interviews: "real graphs are sparse, so list by default; matrix when the graph is dense or the workload hammers edge-existence checks." Judgement plus numbers — that's the whole expected answer.
Building from an edge list — the interview opener
Interview problems hand you edges as pairs. The first six lines of nearly every graph solution convert them into an adjacency list:
from collections import defaultdict
def build_adj(edges, directed=False):
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
if not directed:
adj[v].append(u) # mutual: register BOTH directions
return adj
metro = build_adj([("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")])
print(dict(metro))Result
{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}The whole directed-vs-undirected decision lives in that if not directed line — modelling question 1, as code. For weighted graphs, append (neighbour, weight) tuples instead; that's the exact shape Dijkstra will consume later. Quick sanity check on the output: total list entries = 8 = 2 × 4 edges ✓ (every undirected edge appears twice — remember this; it explains a fact two sections down).
💡 Grids are graphs in disguise: each cell is a vertex, and "up/down/left/right" is the edge rule, computed on the fly. "Number of islands", maze problems, chessboard puzzles — all graph questions where nobody hands you edges. Seeing the hidden graph is the skill.
Wait — so what exactly IS a tree?
A quick puzzle that ties two lessons together. A connected undirected graph has V = 6 vertices and exactly 5 edges. Can it contain a cycle?
Reason it out: connecting 6 vertices needs at least 5 edges (each new vertex needs at least one edge joining it in). We have exactly 5 — zero slack. A cycle would need one spare edge beyond the minimum. So: no cycle possible. And a graph that is connected and acyclic is... a tree.
Any two of {connected, acyclic, E = V−1} force the third. A tree is just a graph living on the edge of disconnection — the leanest possible way to connect everything. This little theorem works for a living: it powers cycle-detection-by-counting, explains why spanning trees have V−1 edges, and is the stopping condition of Kruskal's MST algorithm (algorithms lesson 10).
Degrees and the handshake fact
A vertex's degree is its edge count. Directed graphs split it: in-degree (arrows in) and out-degree (arrows out). Two small facts do outsized work:
The handshake fact: in an undirected graph, Σdegrees = 2E — you verified it on the adjacency list above (8 entries, 4 edges). Why: every edge donates +1 to exactly two vertices. Party version: count each person's handshakes and add them up — every handshake got counted twice. Corollary interviewers like: the number of odd-degree vertices is always even.
In-degree zero: in a directed graph, a vertex with in-degree 0 has no prerequisites — nothing points at it. "Repeatedly take an in-degree-0 vertex" is Kahn's topological sort, the course-scheduling algorithm waiting in the BFS/DFS lesson. File the phrase now.
What if...?
What if a vertex has no edges at all? Legal — an isolated vertex. But notice: a defaultdict built only from edges has never heard of it! Loop over all V vertices (not just the dict's keys) when the problem includes loners, or seed the dict with every vertex first.
What if the graph is disconnected? Very common, and silently fatal to code that traverses from one start vertex and assumes it saw everything. The fix pattern (traverse from every unvisited vertex) is exactly how "number of connected components" is counted — next course.
What if an edge connects a vertex to itself, or appears twice? Self-loops and parallel edges exist in the wild (a page linking to itself; two flights between the same cities). Most interview problems assume a simple graph — neither — and stating that assumption aloud costs three seconds and reads as care.
What if I need edge weights in the matrix? Store the weight instead of 1 — and now 0 becomes ambiguous (no edge, or a zero-cost edge?). Use None/∞ for absence. Small detail, classic bug.
Common mistakes
- Registering an undirected edge in one direction only — half the graph vanishes for traversals.
- Modelling a one-way relation (follows, prerequisites) as undirected — inventing connections.
- A matrix for a sparse graph — 10 crore cells for 30,000 edges.
- Forgetting isolated vertices when building from edges.
- Assuming connectivity — always ask "could this graph be in pieces?"
- Confusing path length (edges) with the number of vertices on the path — a persistent off-by-one in distance answers.
How do I recognise graph problems?
- The data is about relationships — friends, follows, routes, dependencies, prerequisites → graph, and your first move is the six-line adjacency-list builder.
- A grid with movement rules → implicit graph; neighbours computed from coordinates.
- "can A reach B / are they connected / how many groups" → traversal or union-find (lesson 11).
- "order tasks with dependencies" → directed graph + topological sort.
The universal first question when you spot a graph: directed or undirected? weighted or not? Say it aloud — those two bits choose the storage AND the algorithm.
Quick revision
| Concept | One-liner |
|---|---|
| Graph | vertices + edges; cycles and islands allowed, no root |
| Two modelling bits | directed? weighted? — decide before storing |
| Adjacency list | O(V+E); the default — real graphs are sparse |
| Adjacency matrix | O(V²); O(1) edge checks; dense graphs |
| Tree, redefined | connected + acyclic ⟺ connected + E = V−1 |
| Handshake fact | Σdegrees = 2E; odd-degree vertices come in pairs |
One thing to remember
A graph is just things and connections — your two decisions are direction and weight, and your default storage is the adjacency list, because the real world is sparse.
Practice Zone — PYQs from real selection rounds
Six MCQs, then three foundations: build the adjacency list, argue list-vs-matrix with actual numbers, and compute in/out degrees from raw edges.
A graph differs from a tree because a graph:
Asked in
For a graph of 10,000 vertices and 30,000 edges (sparse), the adjacency MATRIX would need:
Asked in
The one operation where an adjacency MATRIX beats a list is:
Asked in
In an UNDIRECTED graph, the sum of all vertex degrees equals:
Asked in
Which real relationship is naturally a DIRECTED graph?
Asked in
A connected undirected graph has V vertices and exactly V − 1 edges. What do you know for certain?
Asked in
Hands-on tasks:
Build an adjacency list for the undirected graph with edges [(0,1), (0,2), (1,3), (2,3), (3,4)] and print it.
Asked in
For the same graph as list and matrix, state the cost of: (1) "is there an edge 2—4?", (2) "list all neighbours of 3", (3) total memory. n = 5, e = 5.
Asked in
Given directed edges [(0,1), (0,2), (2,1), (3,0), (1,3)], compute each vertex's in-degree and out-degree. Which vertex could be a 'celebrity' (in-degree high, out-degree 0)?
Asked in
FAQ
This lesson stored graphs but never walked one. Where's BFS/DFS?
In the Algorithms course — traversal is an algorithm on top of this structure. The split is deliberate: every traversal's O(V + E) cost analysis assumes an adjacency list underneath, so the representation comes first.
How do social networks store graphs with 100 crore users?
Conceptually still adjacency lists — per-user follower lists — sharded across machines and cached. The matrix was never an option: (100 crore)² cells exceeds all storage on Earth. Sparse thinking scales; dense thinking doesn't.
What's a DAG, and why does the term appear everywhere?
Directed Acyclic Graph — arrows, no cycles. It's the shape of every dependency system: prerequisites, build pipelines, spreadsheets. Its superpower is topological order (a valid processing sequence), which exists if and only if the graph is a DAG — the heart of the course-schedule problem coming in BFS/DFS.
When is the matrix genuinely the right choice?
Dense graphs (E close to V²), tiny graphs where V² is trivial, and algorithms that hammer "is there an edge u–v?" — plus Floyd-Warshall-style all-pairs DP, which is naturally matrix-shaped. Sparse + traversal-heavy — the common case — stays with the list.
Connections modelled and stored. Next, a tree where the path itself spells the answer — Lesson 10: Tries →