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.
Graph ready.
| A | B | C | |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 1 | 0 |
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: Click "Add Node" and place them on the canvas.
- Add Edges: Connect two nodes.
- Toggle Directed: Switch to "Directed" mode.
- Randomize: Generate complex structures instantly.
Legend
Node (Vertex)
Edge (Connection)
Directed Edge (A → B)
* List: efficient for sparse graphs, O(V+E) space.
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)
Frequently Asked Questions
Adjacency List vs Adjacency Matrix?
Adjacency Matrices are O(V²) space and good for dense graphs. Adjacency Lists are O(V+E) space and better for sparse graphs (most real-world networks).
What is a Sparse vs Dense Graph?
A graph is sparse if the number of edges is close to the number of vertices. It is dense if the number of edges is close to the maximum possible (V²).
Directed vs Undirected Graphs?
In directed graphs, edges have a specific direction (A to B). In undirected graphs, edges are bidirectional.