4.2.4.1 - Graphs and adjacency representations (Python)

Nodes, edges and weighted directed graphs

A graph represents relationships that need not form a simple sequence or hierarchy.

Vertices can represent stations, people or web pages; edges can represent travel links, friendships or hyperlinks. In an undirected graph, an edge connects its endpoints both ways. In a directed graph, an arc has an origin and destination: A → B does not imply B → A. A weighted graph attaches a value to an edge, such as a distance, cost or journey time. State what the weights measure; a weight is not necessarily a geometric length.

[DIAGRAM: asset_slug: graph_routes; description: Directed weighted graph with arcs A to B cost 4, A to C cost 2, B to C cost 1 and C to A cost 3]

The diagram contains three vertices and four directed arcs. A can reach C directly at cost 2; C can reach A directly at cost 3. Those are separate arcs with different costs. Graphs can represent cycles, such as A → C → A. A social friendship graph might instead be undirected and unweighted. Choose direction and weights from the relationship's meaning, rather than drawing arrows or numbers arbitrarily.

Adjacency matrices

An adjacency matrix uses a row for the origin and a column for the destination to store each possible connection.

Agree a fixed vertex order, here A, B, C. For an unweighted graph, 1 can mean an edge exists and 0 no edge. For our weighted graph use None for no arc, so zero can remain a legitimate weight if a later problem permits it.

In Python, matrix[0][2] gives the weight of A → C. The matrix is not symmetric because the graph is directed. An undirected graph's entries match across the main diagonal: the same edge is represented at [i][j] and [j][i]. A diagonal entry represents an edge from a vertex to itself; diagonal absence is a stated property here, not a universal graph rule.

For n vertices, a matrix reserves $n^2$ entries even when most connections are absent. Testing one known pair's connection is a direct indexed lookup. Finding all outgoing neighbours requires scanning that vertex's entire row. Adding a vertex requires changing the matrix's shape and preserving the vertex-index mapping.

Adjacency lists and representation trade-offs

An adjacency list stores each vertex's actual neighbours rather than reserving space for every possible pair.

For an unweighted graph, each vertex maps to a list of neighbours. For a weighted graph, store (neighbour, weight) pairs:

routes = {"A": [("B", 4), ("C", 2)],
          "B": [("C", 1)],
          "C": [("A", 3)]}