22 of 32 · 6 min
When anything can connect to anything
A tree has one parent per node and no cycles. Drop both restrictions and you have a graph, which is what most interesting data actually is.
Friendships. Roads between cities. Web pages linking to each other. Tasks that depend on other tasks. Flights. None of these are trees, because they contain loops and things connect in both directions.
The vocabulary
Nodes are vertices, connections are edges.
- Directed or not: a road may be one way, a friendship is usually mutual.
- Weighted or not: an edge may carry a distance, a cost, a capacity.
- Cyclic or not: a graph with no cycles and direction is a DAG, which is what a dependency list is.
A tree is a connected graph with no cycles, which is why everything that works on graphs also works on trees, and not the other way around.
Two ways to store one
Adjacency list: for each vertex, the list of its neighbours.
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C'],
}Adjacency matrix: a grid where cell (i, j) says whether an edge exists.
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0| Adjacency list | Adjacency matrix | |
|---|---|---|
| Space | O(V + E) | O(V squared) |
| Is there an edge A to B? | O(degree) | O(1) |
| List A's neighbours | O(degree) | O(V) |
| Good when | edges are few | edges are many |
Most real graphs are sparse: a social network with a million users does not have a million connections per user. So the adjacency list is the default, and a matrix with a trillion mostly empty cells is the alternative.
What gets asked
The questions are nearly always one of a small set: is there a path, what is the shortest path, are there cycles, which parts are disconnected, what order can these dependencies be done in.
Every one of those is answered by walking the graph in a particular way, which is the next page.