Graphs

A graph is a set of things (nodes) plus the connections between them (edges). Road maps, social networks, web links, package dependencies and flight routes are all graphs. Edges can be one-way or two-way, and they can carry a weight such as distance or cost. In code you usually store a graph as an adjacency list, where each node keeps a list of its neighbors, which is compact when most nodes have few connections. The alternative is an adjacency matrix, a grid that answers “is there an edge from A to B?” instantly but uses space for every possible pair. A huge number of problems become easier once you notice they’re secretly graph problems.