Graph representations

Vertices + edges. No root, cycles allowed. How you store it sets the cost of everything after.

Two representations, mirror-image costs

Watch a graph get built

Each edge appends to both endpoints' neighbor lists.

Real graphs are sparse → list wins

Sparse graph, 4000 vertices: 437 KB (list) vs 125 MB (matrix) → 286×. Matrix also makes every traversal O(V²) instead of O(V+E).

Also: directed/undirected, weighted

• Directed: edges have direction (matrix asymmetric)
• Weighted: store cost with each neighbor / in the cell
• The weighted directed adjacency list runs most of this tier

Takeaway

Default to the adjacency list — real graphs are sparse. Every algorithm ahead is O(V+E) because of it. Next: BFS and DFS.