Graph Representation
A graph is one of the most powerful and versatile data structures in computer science. It models pairwise relationships between objects: cities and roads, users and friendships, tasks and dependencies.
Formally, a graph G = (V, E) consists of a set of vertices (nodes) V and a set of edges E. Each edge connects two vertices.
Key Properties
| Property | Options |
|---|---|
| Direction | Directed (edges have direction) vs Undirected |
| Weights | Weighted (edges have costs) vs Unweighted |
| Cycles | Cyclic (contains cycles) vs Acyclic (no cycles — trees, DAGs) |
| Connectivity | Connected (all nodes reachable) vs Disconnected |
Adjacency Matrix
An N×N matrix where matrix[u][v] = weight if edge (u, v) exists, else 0.
A B C
A [0, 1, 1]
B [1, 0, 0]
C [1, 0, 0]- Space: O(V²) — expensive for sparse graphs
- Check edge: O(1) — instant lookup
- Get neighbors: O(V) — must scan the whole row
- Best for: Dense graphs where V is small
Adjacency List
Each vertex maps to a list of its neighbors (and weights if applicable).
A → [B, C]
B → [A]
C → [A]- Space: O(V + E) — efficient for sparse graphs
- Check edge: O(degree) — scan neighbor list
- Get neighbors: O(degree) — iterate the list
- Best for: Sparse graphs (most real-world graphs)
Real-World Examples
- Social networks: Users = vertices, friendships = undirected edges
- Web graph: Pages = vertices, hyperlinks = directed edges
- GPS maps: Intersections = vertices, roads = weighted undirected edges
- Package dependencies: Packages = vertices, “depends on” = directed edges
- Neural networks: Neurons = vertices, synapses = weighted directed edges