The idea: nodes and the connections between them
Think of a graph as a map of dots and lines. Each dot is a vertex — a person, a city, a web page, a task. Each line is an edge — a friendship, a road, a hyperlink, or a "must happen before" relationship. That is the whole model. Trees and linked lists are really just graphs with extra rules; a plain graph makes no promise about shape, so a vertex can connect to none, one, or thousands of others, and cycles are allowed.
The power is that once you notice something is "items plus relationships," a whole library of graph algorithms opens up: shortest paths, reachability, cycle detection, ordering. Recognizing the graph hiding inside a word problem is often the hardest and most valuable step, and it gets much easier once you have watched a traversal move across the nodes a few times.
Directed, undirected, and weighted edges
Edges carry meaning through two properties. Direction: an undirected edge is mutual (a Facebook friendship), while a directed edge goes one way (a Twitter follow, or a course prerequisite). Weight: an unweighted edge just says "connected," while a weighted edge attaches a number — distance, cost, time, or capacity. A road map is a weighted undirected graph; a build system is a directed graph whose edges mean "depends on."
These choices decide which algorithms apply. Dijkstra's needs non-negative weights, topological sort needs a directed acyclic graph (DAG), and detecting a cycle in a directed graph differs from doing it in an undirected one. Naming the edge type first is how you pick the right tool.
Adjacency list vs adjacency matrix
You mainly store a graph two ways. An adjacency list keeps, for each vertex, a list of its neighbors — compact when edges are few (a sparse graph), which describes most real-world data. An adjacency matrix is a V×V grid where cell [u][v] marks whether an edge exists — giving O(1) edge lookups and clean math, but costing O(V²) space even when the graph is nearly empty.
Rule of thumb: default to an adjacency list. It uses O(V + E) space and lets you iterate a vertex's neighbors in time proportional to how many there are, which is exactly what BFS and DFS need. Reach for a matrix when the graph is dense, very small, or when you need constant-time "is there an edge?" checks or matrix operations.
from collections import defaultdict, deque
class Graph:
def __init__(self, directed=False):
self.adj = defaultdict(list)
self.directed = directed
def add_edge(self, u, v):
self.adj[u].append(v)
if not self.directed:
self.adj[v].append(u)
def bfs(self, start):
seen, order, q = {start}, [], deque([start])
while q:
node = q.popleft()
order.append(node)
for nxt in self.adj[node]:
if nxt not in seen:
seen.add(nxt)
q.append(nxt)
return orderV = vertices, E = edges. Adjacency lists win on sparse graphs (E far below V²), which covers most real data; matrices win on dense graphs and constant-time edge checks.
When to use it
- Modeling anything where items connect: social graphs, road and transit maps, computer networks, or web-page links.
- Finding shortest or cheapest paths between points (GPS routing, network latency) using BFS, Dijkstra, or A*.
- Ordering tasks with dependencies — build systems, course prerequisites, package installs — via topological sort on a DAG.
- Answering reachability and connectivity questions: can A reach B, how many connected components exist, is there a cycle?
Watch out for
- Using an adjacency matrix for a large sparse graph, burning O(V²) memory when an adjacency list would use only O(V + E).
- Forgetting to track visited nodes during traversal, so cycles cause infinite loops or exponential repeated work.
- Mixing up directed and undirected edges — adding an edge only one way when the relationship is mutual, or both ways when it isn't.
Graphs are one of the highest-value interview topics because many medium and hard problems are graphs in disguise. Interviewers rarely ask you to define a graph — instead they hand you a grid, a list of prerequisites, or a set of word transformations and expect you to recognize the underlying graph, choose a representation, and run BFS, DFS, topological sort, union-find, or Dijkstra. What they watch for is whether you spot the model quickly, handle visited-state correctly, reason about V and E in your complexity analysis, and cover edge cases like disconnected components, cycles, and self-loops. Being able to build an adjacency list on the spot signals genuine comfort with the topic.