Graphs: Adjacency List

A graph consists of nodes and edges. A node-based adjacency representation stores the list of neighbors for each node. Sparse graphs therefore require $O(n + m)$ space.

An n x n matrix is $O(n^{2})$ and quick for dense graphs, allowing edge queries in $O(1)$.

In Java: Map> or List>.

A grid as a graph: Number of Islands [1].

Where used

Social networks, microservice dependencies, roadmaps, knowledge graphs, build dependency graphs. Adjacency lists dominate in memory for sparse graphs.

Depth

In the neighbor list representation, each node stores a collection of directly reachable targets. The memory requirement is proportional to the number of nodes plus edges, making it particularly suitable for sparsely populated graphs.

Enumerating all neighbors costs proportional to the degree of the node. However, checking for a specific edge can be linear in degree if the neighbor collection does not have an additional hash or search structure.

In undirected graphs, a logical edge is often stored in both directions. Loops and parallel edges require a conscious modeling decision, as they influence degree calculation and algorithms.

Difficulty levels

1. Build neighbor collections from a set of edges.
2. Analyze space and query costs based on node degree.
3. Correctly account for duplicate storage of undirected edges.

Pitfalls

The number of stored entries for undirected edges is usually twice the logical edge count. A missing target set for isolated nodes causes them to disappear from the graph model.