Graphs
Vertices connected by edges. The general model for networks, maps, dependencies, and relationships.
Level: intermediate
What is it?
A graph is a set of vertices (nodes) and edges connecting pairs of them. Edges can be directed or undirected and can carry weights. Common representations are an adjacency list (each vertex holds a list of neighbors) and an adjacency matrix (a V × V grid). Special cases include trees (connected, no cycles), DAGs (directed, no cycles), and bipartite graphs.
Why does it matter?
Graphs model anything with relationships: roads, computer networks, web links, social connections, task dependencies, and state machines. Once a problem is drawn as a graph, standard algorithms — traversal, shortest paths, spanning trees, topological sort — apply directly.
Mental model
A subway map. Stations are vertices and tracks are edges. The map ignores geography and keeps only what matters: what connects to what, and sometimes how long or expensive each link is.
How it works
- Directed edges have a direction (A → B); undirected edges do not. Weighted edges carry a cost or distance.
- Adjacency list: O(V + E) space, fast iteration over neighbors — best for sparse graphs.
- Adjacency matrix: O(V²) space, O(1) edge test — best for dense graphs or small V.
- A path is a sequence of edges; a cycle returns to its start. A DAG has none, so it can be topologically ordered.
- Connected components, degrees, and in/out edges are the first questions to ask about any graph.
- Network topologies, routing tables, and dependency graphs in build systems are all graphs.
Steps
- Identify the vertices
- Identify the edges and their direction
- Attach weights if costs matter
- Choose a representation
- Run a traversal or path algorithm
Code example: An adjacency list
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["D"],
"D": [],
}
edges = sum(len(nbrs) for nbrs in graph.values())
print(edges) # 4 directed edges
print(graph["A"]) # neighbors of A: ['B', 'C']Complexity and trade-offs
Time: Traversals O(V + E); edge test O(1) (matrix) or O(degree) (list)
Space: O(V + E) for a list; O(V²) for a matrix
Trade-offs
- Lists suit sparse graphs, which most real ones are
- Matrices give constant-time edge checks and simple algorithms for dense graphs
Real-world usage
- Routing and network topology
- Social networks, recommendation, and search
- Build systems, package managers, and task schedulers (DAGs)
Common mistakes
- Using a matrix for a huge sparse graph.
- Forgetting to mark visited vertices and looping forever on cycles.
- Mixing up directed and undirected edges when adding neighbors.
Interview questions
Adjacency list or adjacency matrix?
Use a list for sparse graphs (E much smaller than V²): it saves space and iterates neighbors quickly. Use a matrix for dense graphs or when you need O(1) edge queries and V is small.
What is a DAG and why does it matter?
A directed acyclic graph has no directed cycles, so its vertices can be topologically sorted. It models dependencies such as build steps, course prerequisites, and task pipelines.
How do you detect a cycle in a directed graph?
Run a depth-first search, tracking vertices on the current recursion path. Reaching a vertex already on the path means a cycle. Alternatively, Kahn's algorithm fails to process all vertices if a cycle exists.
| Representation | Space | Edge test | List neighbors |
|---|---|---|---|
| Adjacency list | O(V + E) | O(degree) | O(degree) |
| Adjacency matrix | O(V²) | O(1) | O(V) |