Modelling with a graph

Two ways to store it in memory

The problem: how to encode "who is connected to whom"

A graph does not have the ready-made structure of a tree. To put it in memory, there are two main representations, with opposite trade-offs. Let's take this small undirected graph as an example:

        (A)------(B)
         |        |
         |        |
        (C)------(D)

Neighbourhoods: A: B,C — B: A,D — C: A,D — D: B,C.

Representation 1: the adjacency matrix

We build a square table: the cell (row X, column Y) is 1 if there is an edge between X and Y, and 0 otherwise.

        A   B   C   D
      +---+---+---+---+
  A   | 0 | 1 | 1 | 0 |
      +---+---+---+---+
  B   | 1 | 0 | 0 | 1 |
      +---+---+---+---+
  C   | 1 | 0 | 0 | 1 |
      +---+---+---+---+
  D   | 0 | 1 | 1 | 0 |
      +---+---+---+---+

For an undirected graph, the matrix is symmetric (the edge A-B appears at (A,B) and at (B,A)).

sommets = ["A", "B", "C", "D"]
matrice = [
    [0, 1, 1, 0],   # A
    [1, 0, 0, 1],   # B
    [1, 0, 0, 1],   # C
    [0, 1, 1, 0],   # D
]
# "Are A and D connected ?"  ->  matrice[0][3] == 0  -> no

Advantage: knowing whether two vertices are connected is immediate (a single cell to read). Disadvantage: the matrix takes up n x n cells, even if the graph has very few edges. For a social network of millions of people, this is unmanageable.

Representation 2: the adjacency list

For each vertex, we simply store the list of its neighbours. In Python, a dictionary is perfectly suited to this.

graphe = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}
# the neighbours of B ?  ->  graphe["B"]  ->  ['A', 'D']

Advantage: we store only the edges that exist. For a graph with low density (few edges relative to the number of vertices), this is infinitely more economical. Disadvantage: to know whether A and D are connected, we must scan the list of A's neighbours.

Which one to choose?

   Many edges ("dense" graph)            ->  adjacency matrix
   Few edges ("sparse" graph)            ->  adjacency list

Criterion	Matrix	List
Memory used	`n x n`	`n + edges`
Test an edge `X-Y`	immediate	scan neighbours
List a vertex's neighbours	scan 1 row	immediate

In practice, most real graphs (social networks, roads) are sparse: so we almost always use the adjacency list. It is the one we will use for traversals.

In summary