Modéliser avec un graphe

Deux façons de le stocker en mémoire

Le problème : comment coder « qui est relié à qui »

Un graphe n'a pas la structure toute tracée d'un arbre. Pour le mettre en mémoire, il existe deux grandes représentations, avec des compromis opposés. Prenons ce petit graphe non orienté comme exemple :

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

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

Représentation 1 : la matrice d'adjacence

On construit un tableau carré : la case (ligne X, colonne Y) vaut 1 s'il existe une arête entre X et Y, et 0 sinon.

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

Pour un graphe non orienté, la matrice est symétrique (l'arête A-B apparaît en (A,B) et en (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
]
# "A et D sont-ils relies ?"  ->  matrice[0][3] == 0  -> non

Avantage : savoir si deux sommets sont reliés est immédiat (une seule case à lire). Inconvénient : la matrice occupe n x n cases, même si le graphe a très peu d'arêtes. Pour un réseau social de millions de personnes, c'est ingérable.

Représentation 2 : la liste d'adjacence

Pour chaque sommet, on stocke simplement la liste de ses voisins. En Python, un dictionnaire s'y prête parfaitement.

graphe = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}
# les voisins de B ?  ->  graphe["B"]  ->  ['A', 'D']

Avantage : on ne stocke que les arêtes qui existent. Pour un graphe peu dense (peu d'arêtes par rapport au nombre de sommets), c'est infiniment plus économe. Inconvénient : pour savoir si A et D sont reliés, il faut parcourir la liste des voisins de A.

Lequel choisir ?

   Beaucoup d'aretes (graphe "dense")   ->  matrice d'adjacence
   Peu d'aretes (graphe "creux")        ->  liste d'adjacence

Critère	Matrice	Liste
Mémoire utilisée	`n x n`	`n + aretes`
Tester une arête `X-Y`	immédiat	parcours voisins
Lister les voisins d'un sommet	parcourir 1 ligne	immédiat

En pratique, la plupart des graphes réels (réseaux sociaux, routes) sont creux : on utilise donc presque toujours la liste d'adjacence. C'est celle qu'on emploiera pour les parcours.

En résumé