A graph is a set of things (vertices, or nodes) and connections between them (edges). Road maps, social networks, the web's links, flight routes and the steps of a recipe are all graphs. Trees are a special kind of graph with no loops.
Edges can be undirected (a friendship goes both ways) or directed (you can follow someone who doesn't follow you back; a one-way street). They can also carry a weight, like the distance or travel time of a road.
The usual way to store a graph is an adjacency list: for each vertex, the list of vertices it connects to. In Python, a dictionary of lists does it.
roads = {
"Home": ["Shop", "Park"],
"Shop": ["Home", "School"],
"Park": ["Home"],
"School": ["Shop"],
}
print(roads["Shop"])
print(len(roads["Home"]))['Home', 'School'] 2
The other way is an adjacency matrix: a grid with a row and a column per vertex, and a 1 where two are connected. Checking one pair is instant, but it needs space for every possible pair, so it suits small or very connected graphs. Most real graphs (most people aren't friends with most people) are sparse, and lists win.
The number of edges at a vertex is its degree. A path is a route along edges, and a cycle is a path that comes back to where it started. The algorithms course shows how to search a graph for a path.
"A follows B" on a social app, where B doesn't have to follow back. What kind of edge is that?
| Vertex / edge | A thing / a connection between two things. |
|---|---|
| Directed / undirected | One-way / both ways. |
| Weighted | Edges carry a number: distance, cost, time. |
| Adjacency list | Each vertex's neighbours. Best for most graphs. |
| Adjacency matrix | A grid of every pair. Quick to check, big. |