Graph Representations

Graph Basics

A graph models things and their connections: vertices (nodes) joined by edges. They represent road maps, social networks, and dependency chains.

Edges can be directed (one-way) or undirected (mutual), and may carry a weight representing distance, cost, or capacity.

Common Pitfall: Using an adjacency matrix for a large sparse graph. A million-node graph with few edges wastes $O(V^2)$ space on empty cells.

Memory Trade-offs

Choosing a graph representation is a classic space-time trade-off between two standard structures.

An adjacency matrix is a $V \times V$ grid where entry $(i, j)$ records the connection. It allows $O(1)$ edge checking, suiting dense graphs.

An adjacency list stores each vertex's neighbors. It uses $O(V + E)$ space, suiting sparse graphs.