Graph Representations

Hook

A road atlas can list roads, list neighbors or mark every pair on a grid.

Watch

The same links, three representations. Edit the graph JSON to add a cycle, isolate a vertex or change an edge weight. Nodes are numbered from zero.

How it works

1. Read each validated edge.
2. Populate the neighbor lists.
3. Write matrix entries, preserving absent versus zero-cost edges.

Try it

Predict the next frontier decision or edge operation before revealing it. Compare a connected graph with the same graph after removing an important edge.

Complexity

Lists take O(V+E) space; a matrix takes O(V²). An adjacency list spends storage on vertices and existing edges. A matrix indexes pairs directly but allocates every possible pair. The counters count teaching operations; animation duration is not a CPU benchmark.

Code

The four references show the core operation. Adjacency-list inputs use zero-based vertex indices. Weighted references use (neighbor,weight) pairs or explicit edge triples. Validate the graph assumptions before calling standalone code.

When to use

Use a matrix for dense pair lookups and a list for sparse neighbor traversal.

Interview pitfalls

A zero-cost edge exists; null means absent.

Quiz

Check the graph assumptions, invariant and boundary conditions below.