Vertices and edges
A graph is a set of vertices joined by edges. Here each town is a vertex and each road is an edge: 6 vertices, 5 edges. Swap towns for people and roads for friendships, and the same picture is a social network.
Every road here is two-way: you can drive from A to B and back again. A graph whose edges work both ways is undirected, so the edge A–B is the same edge as B–A.
Storing a graph
To store a graph, a program can keep an adjacency list: for each vertex, a list of its neighbours, the vertices one edge away. Town C's line reads A B D, because roads lead from C to A, B and D.
An adjacency matrix is a grid with one row and one column per vertex. Row B, column C holds 1 because a road joins B and C; 0 means no road. Two-way roads make it symmetric: row C, column B is 1 too.
The matrix needs a cell for every pair of towns: 6 × 6 = 36. The list stores each road twice, once per end: 10 entries. With few roads, lists save memory; a matrix answers "is B next to C?" in one look.
Paths and cycles
A path is a route that follows edges from vertex to vertex. Driving D → C → B is a path of two edges. Map apps search for paths like this, and the internet's routers do too, as the networking course shows.
A cycle is a path that ends where it started without reusing a road. A → B → C → A is a cycle: drive it and you are back at A after three roads.
No road links E or F to the other towns. Each group of vertices that can all reach one another is a connected component, so this graph has two: A, B, C, D and E, F.
Close road B–C and the cycle is gone. A connected graph with no cycles is a tree: here 4 towns, 3 roads and exactly one path between any two towns. Hang it from A and it is the shape from the Trees lesson.
Direction and weight
Now make C → D one-way. An edge with a direction is a directed edge, and the graph becomes directed. Row C, column D stays 1, but row D, column C turns 0, and D's list is now empty.
Give each road its length and the graph is weighted. The matrix stores each weight instead of 1, with – where there is no road, and each list entry carries its weight. A → C → D is 3 + 5 = 8 km.
Try it in the Python prompt
;; step 1/11 · Vertices and edges
>>> towns = ["A", "B", "C", "D", "E", "F"]
>>> roads = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D"), ("E", "F")]
>>> len(towns), len(roads)
(6, 5)
The towns, roads and distances are a made-up example, kept small so the whole matrix fits on one card. For V vertices and E edges, an adjacency matrix always has V × V cells, while an adjacency list holds 2E entries for an undirected graph (E for a directed one), plus one list per vertex.