Graphs

An adjacency list maps each vertex to the vertices it has edges to. MIT’s 6.006 notes use an array for that map when vertices are numbered 0 to V−1 and a hash table otherwise, with an array or linked list per vertex, since algorithms mostly iterate over neighbours. The whole graph fits in Θ(V+E) space, listing a vertex’s neighbours takes time proportional to its degree, and breadth-first search runs in time proportional to V+E. Checking whether one particular edge exists means scanning a neighbour list, unless each list is itself a hash set.

An adjacency matrix is an n×n grid whose cell (i, j) says whether there is an edge from i to j, or holds its weight. Adding an edge or checking one is O(1), but the grid always takes O(n²) space, which is wasteful for sparse graphs where most cells are empty. Stanford’s CS106B notes sum it up: an adjacency list for sparse graphs, a matrix for dense ones.

In code, a graph is usually a map of lists, such as a Python dict from each vertex to a list of neighbours, exactly as in MIT’s examples. When the graph itself is the data to store and query, such as people and who follows whom, graph databases keep the vertices and edges on disk and answer questions by walking them; see the graph databases page.