Graph Representation
Visualize how graphs are stored in memory using Adjacency Matrices and Adjacency Lists. Build your own graph and see the representations update in real-time.
3 NODES · 3 EDGES
MOVE
Adjacency matrix — O(V²) space, O(1) lookup
A
B
C
A
B
C
Drag the nodes to rearrange. Switch to NODE or EDGE to add to the graph, and the representation below follows.
Tool
Edges
Weights
Show
Intuition
A Graph is a non-linear data structure consisting of Nodes (vertices) and Edges (connections between nodes). Unlike trees, graphs don't have a strict hierarchy—any node can connect to any other node.
Think of a Graph like a Social Network:
- Nodes: People (Users)
- Edges: Friendships or Follows
Concept
Key Terminology
- Vertex (V): A point or node in the graph.
- Edge (E): A link between two vertices.
- Directed Graph: Edges have a direction (A → B).
- Undirected Graph: Edges have no direction (A — B).
- Weighted Graph: Edges have values (weights).
Graph Representations
A 2D array adj[V][V].
Great for dense graphs and O(1) edge lookups.
An array of lists.
Saves space for sparse graphs.
How it Works
Adjacency Matrix Logic:
We create a V x V grid. If node 0 connects to node 2, we mark row 0, column 2 as 1 (or true).
Adjacency List Logic:
We create an array where index 0 holds a list: [2, 5, ...]. This means node 0 connects to 2 and 5.
Step-by-Step Breakdown
Use the interactive builder above to experiment:
- Add Nodes: Choose the Node tool and click the canvas.
- Add Edges: Choose the Edge tool and click two nodes.
- Move or Delete: The Move tool drags nodes; the Delete tool removes the node or edge you click.
- Direction and Weights: Set Edges to Directed and the matrix is no longer symmetric; set Weights to On and it holds each weight instead of 1.
- Compare Representations: Switch Show between Matrix and List.
- Random and Reset: Generate a random graph, or go back to the three-node triangle.
Trace: building the triangle A, B, C
addVertex A, B, C
Each call finds no entry for its vertex and creates an empty list. The existence check is what makes calling addVertex twice for the same vertex harmless.
A:[] B:[] C:[]
addEdge(A, B)
Two pushes: B onto the list of A, then A onto the list of B. One undirected edge, two entries.
A:[B] B:[A] C:[]
addEdge(B, C)
C onto the list of B, B onto the list of C.
A:[B] B:[A,C] C:[B]
addEdge(C, A)
A onto the list of C, C onto the list of A. The list now holds 3 keys and 6 entries: every undirected edge is stored twice, V + 2E in all, which is the O(V + E) space.
A:[B,C] B:[A,C] C:[B,A]
as a matrix
The same graph as a 3 × 3 grid: 9 cells, 6 of them 1, mirrored across the diagonal because each edge was written in both directions. The grid costs V² cells before a single edge exists, which is why it suits dense graphs.
9 cells, 6 set
edge C–A?
The matrix answers from one cell, row C, column A. The list scans the entries of C until it meets A — here the second of two, and up to V − 1 entries in the worst case. That is the O(1) best and O(V) worst.
1 cell vs 2 entries
directed
Drop the second push and the same three calls store one entry per edge, and the matrix loses its mirror: A→B is set, B→A is not.
A:[B] B:[C] C:[A]
When to Use
Use Adjacency List (Most Common):
- When the graph is Sparse (Edges << V²).
- When you need to iterate over all neighbors of a node efficiently.
Use Adjacency Matrix:
- When the graph is Dense (Edges ≈ V²).
- When you frequently need to check "Is there an edge between u and v?" in O(1) time.
When NOT to Use
- Avoid Matrix if V is large (e.g., > 5000) due to memory usage.
How to Identify
Graph problems often appear as:
- "Find the shortest path..." (BFS/Dijkstra)
- "Are these items connected?" (Union-Find/DFS)
- "Schedule these tasks with dependencies..." (Topological Sort)
Preparing for interviews? This topic is also taught as a pattern:
Graph Representation: Adjacency List
Applying for software engineering roles? Free, no sign-up: