Graphs

Things and the connections between them.

Representing one

A graph is nodes joined by edges, directed or not, weighted or not. An adjacency list stores each node's neighbours and suits sparse graphs, which is almost all real ones.

Road networks, social graphs, dependencies and state machines are all graphs.
A tree is a graph with no cycles and one path between any two nodes.

Traversal

Breadth-first explores by distance using a queue and finds the shortest unweighted path. Depth-first follows one path to its end using a stack and suits cycle detection and ordering.