Graph Representations

A graph is a set of vertices and the edges that join pairs of them, and before any graph algorithm can run, the graph has to be stored. It matters because the representation sets the cost of everything that follows: the same million-junction road network takes four million entries as an adjacency list and a trillion cells as an adjacency matrix. The topic starts with the vocabulary and the three properties every graph is described by, then builds an adjacency list from an edge list one edge at a time. It shows what goes wrong when an undirected edge is stored once, introduces the adjacency matrix, and compares the two with the edge list operation by operation, with density as the deciding question. It then stores one graph both ways in three languages and ends with an exercise on a small rail network.