Skip to main content

Adjacency List vs Adjacency Matrix

What This Concept Is​

An adjacency list stores outgoing edge records per vertex in O(V+E) slots. An adjacency matrix uses O(V²) cells and gives O(1) direct pair lookup; scanning a vertex's possible neighbors costs O(V). An edge list is convenient for whole-edge passes and sorting but does not directly provide fast outgoing-neighbor iteration. CSR stores offsets and contiguous edge arrays for compact static traversal.

These representations are equivalent only when they preserve the required information. A single Boolean or scalar matrix cell cannot retain arbitrary parallel-edge identities without extra structure.

Why It Matters Here​

Algorithm names do not determine runtime independently of representation. BFS on adjacency lists scans stored edges; on a matrix it scans rows. Hash-based neighbor lookup, insertion order and graph updates introduce additional choices.

Concrete Examples​

With V=10,000 and E=30,000, a dense matrix has 100 million cells, versus 10,000 list headers and 30,000 directed entries. At an assumed eight bytes per cell, the matrix's payload alone is 800 million bytes; real runtime overhead is extra. A traversal over every matrix row costs O(V²), even though the graph is sparse.

For shortest distances, parallel edges can sometimes be reduced to their minimum weight. For independent flow channels, capacities may be added for a value-only answer. Neither transformation preserves per-original-edge witnesses automatically. Keep original IDs or explicitly weaken the output contract.

Common Confusion / Misconceptions​

Zero is not a universal absent-edge sentinel: zero-weight routes and zero-capacity records may be legitimate. Use None/infinity or separate presence state as appropriate. An undirected adjacency list normally stores two incidences per physical edge; that does not mean Kruskal should treat it as two independent input edges.

How To Use It​

Select representation from operations, density, mutability and witness needs. Price conversion and validation. The labs copy and validate edge records and construct adjacency lists where needed; returned edge IDs always refer to input positions, not temporary adjacency positions.

Check Yourself​

  1. When is an O(V+E) traversal actually O(V²)?
  2. What information does a Boolean matrix discard?
  3. What happens if a zero-weight edge is treated as absent?
  4. Which representation suits repeated Bellman–Ford passes?

Mini Drill or Application​

Represent the same directed multigraph as an edge list and adjacency lists. Verify all edge IDs occur once in outgoing lists and isolated vertices have empty lists. Design a matrix conversion for distance-only queries, documenting what information it deliberately loses. See P2.

Read This Only If Stuck​

Find adjacency representations, edge identity, and sparse storage in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.