Représenter un graphe : listes d’arêtes, listes d’adjacence et matrices

« Quels sommets peut-on atteindre directement depuis 0 ? » et « Existe-t-il une arête de 0 vers 2 ? » semblent être des questions proches, mais elles peuvent demander des parcours très différents. Une liste d’arêtes cherche parmi toutes les arêtes, une liste d’adjacence consulte la collection du sommet 0, et une matrice d’adjacence peut lire une seule case. Choisir le stockage revient à identifier les questions que l’algorithme pose souvent ; la vue d’ensemble des structures de données suit aussi cette approche par opérations.

Sommets, arêtes et opérations à fournir

Le chapitre sur les graphes d’Open Data Structures définit un graphe orienté par $G=(V,E)$ : $V$ est un ensemble de sommets et chaque arête de $E$ est un couple ordonné $(u,v)$, allant de $u$ vers $v$. On note ici $n=|V|$ et $m=|E|$, avec des sommets identifiés par les entiers 0..n-1.

Une arête non orientée relie deux extrémités ; les permuter ne change pas l’arête. Dans un graphe orienté, u→v et v→u sont distinctes. Un graphe pondéré attribue aussi à chaque arête un poids, par exemple une longueur ou un coût. Un graphe non pondéré ne conserve que les connexions. Un poids nul reste un poids valide : il faut donc distinguer une arête absente d’une arête de poids zéro.

La représentation doit généralement permettre d’énumérer tous les sommets et toutes les arêtes, les voisins sortants d’un sommet, de trouver une arête et son poids, et d’insérer ou de supprimer des arêtes. Pour un graphe orienté, les voisins entrants peuvent aussi être nécessaires. Conserver l’ensemble des sommets séparément permet de garder les sommets isolés, qu’on ne peut pas retrouver à partir des seules extrémités des arêtes.

Il faut également décider ce que signifient des couples d’extrémités répétés. Un graphe simple n’a ni boucle ni arêtes parallèles ; une représentation qui les autorise peut conserver un enregistrement par arête. Une case de matrice contenant un seul poids ne peut pas préserver plusieurs arêtes parallèles et leur identité. L’exemple ci-dessous autorise les boucles, mais fusionne les entrées du même couple orienté en gardant le poids minimal. Il ne conserve donc pas toutes les arêtes d’un multigraphe.

Un même graphe, trois représentations

Prenons les sommets 0, 1, 2, 3 et les arêtes 0→1:4, 0→2:0, 1→2:2 et 2→2:5. Le sommet 3 est isolé ; le sommet 2 porte une boucle.

Une liste d’arêtes conserve des triplets (source, destination, poids) dans un seul tableau. Les listes d’adjacence réservent à chaque sommet sa collection d’arêtes sortantes, sous la forme (voisin, poids) si elles sont pondérées. Dans une matrice d’adjacence, la ligne indique la source et la colonne la destination. Le manuel utilise des booléens pour indiquer la présence d’une arête ; ici, les cases contiennent les poids, ou None si l’arête est absente.

Source / ligne	Enregistrements de la liste d’arêtes	Liste d’adjacence adj[u]	Ligne de la matrice, colonnes 0, 1, 2, 3
0	(0,1,4), (0,2,0)	[(1,4), (2,0)]	[None, 4, 0, None]
1	(1,2,2)	[(2,2)]	[None, None, 2, None]
2	(2,2,5)	[(2,5)]	[None, None, 5, None]
3	Aucun enregistrement	[]	[None, None, None, None]

Le tableau regroupe les enregistrements par source pour faciliter la comparaison. La liste d’arêtes reste pourtant un tableau unique, sans index par source. Avec $n=4$ et $m=4$, elle contient 4 enregistrements ; la représentation par adjacence comprend 4 listes et 4 éléments au total ; la matrice réserve $4^2=16$ cases, dont 4 contiennent des arêtes. On compte ici des enregistrements et des cases, pas des octets.

Pour énumérer les voisins sortants de 0, on examine les 4 enregistrements de la liste d’arêtes, les 2 éléments de sa liste d’adjacence, ou les 4 cases de sa ligne de matrice. Les trois donnent [(1,4), (2,0)]. Le poids de 0→2 vaut 0, alors que la recherche de 2→0 renvoie None. Dans la matrice, tester la présence avec is not None préserve la distinction ; tester la valeur de vérité du poids la ferait disparaître.

Dans un graphe non orienté, chaque arête qui n’est pas une boucle figure habituellement deux fois dans les listes d’adjacence : (v,w) dans adj[u] et (u,w) dans adj[v]. Les deux cases correspondantes de la matrice sont égales. Une liste d’arêtes peut conserver l’arête une seule fois, mais doit vérifier ses deux extrémités pour énumérer les voisins. La fonction de construction ci-dessous conserve une boucle non orientée dans un seul élément d’adjacence. Selon la convention de degré en théorie des graphes, elle contribue néanmoins pour 2 au degré : la longueur de la liste ne donne donc pas le degré dans ce cas.

Le coût dépend des conteneurs et des conventions

La comparaison suivante porte sur les opérations d’arêtes avec un ensemble de sommets fixe. La liste d’arêtes et les listes internes d’adjacence sont des tableaux dynamiques non triés. Chaque case de matrice contient un poids ou un marqueur d’absence. L’indexation, la comparaison des poids et le déplacement d’un élément sont comptés à coût constant. On note $d^+(u)$ le nombre d’éléments d’adjacence sortants stockés pour $u$. Le terme 1 inclut le travail constant lorsque le graphe ou la liste est vide. Les temps sont des bornes au pire cas, sauf pour l’ajout en fin de tableau.

Opération	Liste d’arêtes	Listes d’adjacence	Matrice d’adjacence
Espace total, sommets compris	$\Theta(n+m)$	$\Theta(n+m)$	$\Theta(n^2+n)$
Énumérer tous les voisins sortants de u	$O(m+1)$	$O(d^+(u)+1)$	$O(n+1)$
Chercher u→v ou son poids	$O(m+1)$	$O(d^+(u)+1)$	$O(1)$
Ajouter une arête sans vérifier les doublons	$O(1)$ amorti	$O(1)$ amorti	$O(1)$ pour écrire / remplacer
Trouver une arête par ses extrémités et la supprimer	$O(m+1)$	$O(d^+(u)+1)$	$O(1)$

Pour un graphe non vide, on écrit généralement $\Theta(n^2)$ pour l’espace de la matrice ; le terme $n$ supplémentaire compte aussi les enregistrements des sommets. Les seuls enregistrements d’arêtes prennent $\Theta(m)$, mais un ensemble de sommets indépendant est nécessaire pour conserver les sommets isolés. Les tableaux et tableaux dynamiques expliquent le coût amorti de l’ajout et les décalages lors d’une suppression. Un redimensionnement peut encore copier le tableau entier.

Ajouter sans vérifier les doublons n’a pas le même coût que mettre à jour une arête unique. S’il faut rechercher le couple d’extrémités, fusionner des poids ou rejeter un doublon, la liste d’arêtes et la liste d’adjacence ordinaire paient aussi la recherche. Supprimer une arête non orientée qui n’est pas une boucle demande de modifier les deux listes, en $O(d(u)+d(v)+1)$. Dans une matrice, insérer revient à remplacer la valeur d’un couple d’extrémités ; on ne peut pas y ajouter une arête parallèle indépendante.

Une table de hachage par sommet, avec les voisins pour clés, peut donner un coût espéré $O(1)$ pour la recherche, la mise à jour et la suppression, à condition d’avoir un hachage adapté et une charge contrôlée. Le redimensionnement exige une analyse amortie distincte, et le parcours dépend aussi des compartiments et de la capacité ; voir les tables de hachage. Ces hypothèses diffèrent de celles des listes linéaires du tableau. Si un graphe orienté ne stocke que les listes sortantes, chercher les voisins entrants demande de parcourir toutes les listes en $O(n+m)$. Une seconde représentation d’adjacence, inversée, permet de les énumérer selon le nombre d’arêtes entrantes, mais oblige à maintenir les deux copies à chaque modification.

Lorsque $m$ est bien inférieur à $n^2$, les listes d’adjacence évitent de réserver de nombreuses cases vides. Sur un graphe dense, leur espace se rapproche de l’ordre de grandeur de la matrice, dont l’accès direct aux arêtes devient plus intéressant. Ajouter un sommet est une autre opération : réallouer et recopier une matrice compacte peut coûter $O(n^2)$, au-delà de la simple écriture d’une case décrite dans le tableau.

Construire depuis une liste d’arêtes : que faut-il conserver ?

Le programme utilise les sommets 0..n-1, un entier n positif ou nul, et des poids entiers. L’entrée contient 6 enregistrements, dont trois pour 0→1, avec les poids 7, 4, 4. La fusion garde le poids 4 et laisse 4 arêtes au total. Garder le minimum convient aux arêtes parallèles lorsqu’on ne s’intéresse qu’au coût des plus courts chemins. Cette règle perd l’identité et la multiplicité des arêtes ; elle ne permet ni de compter leurs répétitions, ni de fusionner directement les capacités d’un réseau de flot.

La construction se fait en trois étapes :

1. Vérifier que les extrémités appartiennent à l’ensemble des sommets, puis conserver le poids minimal avec le couple d’extrémités pour clé. Dans le cas orienté, garder l’ordre ; dans le cas non orienté, placer la plus petite extrémité en premier pour fusionner (0,1) et (1,0).
2. Créer une liste d’adjacence vide pour chacun des $n$ sommets, puis une matrice de cases sans arête. Les sommets isolés ont ainsi leur place.
3. Ajouter chaque arête retenue aux listes et à la matrice. Ajouter l’entrée inverse pour une arête non orientée qui n’est pas une boucle ; n’ajouter une boucle qu’une fois.

Avec $r$ enregistrements bruts, la fusion et la construction des listes prennent un temps espéré $O(n+r)$ si les opérations de hachage ont un coût espéré constant et l’ajout aux tableaux un coût amorti constant. La table temporaire de clés occupe $O(m)$. Comme le programme construit aussi une matrice, le temps total de construction est espéré $O(n^2+n+r)$. Pour conserver les arêtes parallèles, supprimer la fusion et ajouter chaque enregistrement. La suppression d’une arête précise demande alors un identifiant d’arête, et la matrice à poids unique doit être remplacée par une structure pouvant contenir plusieurs arêtes.

CPython implémente dict avec une table de hachage redimensionnable. Ces bornes de construction supposent aussi que le hachage et la comparaison des clés ont un coût fixe, avec une répartition adaptée des hachages. Ce ne sont pas des garanties au pire cas pour des entrées quelconques.

Exemple exécutable : les mêmes requêtes sur trois représentations

Enregistrer tout le code dans graph_representations.py, puis lancer python3 graph_representations.py avec Python 3.7 ou une version ultérieure. Le contrat des dictionnaires Python garantit l’ordre d’insertion depuis la version 3.7 ; modifier une clé existante ne change pas sa position. La liste d’arêtes affiche donc les couples d’extrémités dans l’ordre de leur première apparition. Le programme sépare l’énumération des voisins de la recherche d’un poids, vérifie l’accord pour chaque couple de sommets dans les graphes orientés et non orientés, et teste les doublons inversés, les boucles, les sommets isolés, le graphe vide et une extrémité hors limites. Les requêtes portent sur des sommets déclarés.

def build(n, raw_edges, directed=True):
    best = {}
    for u, v, weight in raw_edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("endpoint outside vertex set")
        key = (u, v) if directed else (min(u, v), max(u, v))
        if key not in best or weight < best[key]:
            best[key] = weight
    edges = [(u, v, weight) for (u, v), weight in best.items()]
    adjacency = [[] for _ in range(n)]
    matrix = [[None] * n for _ in range(n)]
    for u, v, weight in edges:
        adjacency[u].append((v, weight))
        matrix[u][v] = weight
        if not directed and u != v:
            adjacency[v].append((u, weight))
            matrix[v][u] = weight
    return edges, adjacency, matrix


def grid_neighbors(row, column, rows, columns):
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        r, c = row + dr, column + dc
        if 0 <= r < rows and 0 <= c < columns:
            yield r, c


n = 4
raw_edges = [(0, 1, 7), (0, 2, 0), (0, 1, 4),
             (1, 2, 2), (2, 2, 5), (0, 1, 4)]
edges, adjacency, matrix = build(n, raw_edges)
print("edges:", edges)
print("adjacency:", adjacency)
print("matrix:")
for row in matrix:
    print(row)


def edge_neighbors(edges, u, directed=True):
    neighbors = []
    for source, target, weight in edges:
        if source == u:
            neighbors.append((target, weight))
        elif not directed and target == u:
            neighbors.append((source, weight))
    return neighbors


def list_neighbors(adjacency, u):
    return list(adjacency[u])


def matrix_neighbors(matrix, u):
    return [(v, weight) for v, weight in enumerate(matrix[u])
            if weight is not None]


def edge_weight(edges, u, v, directed=True):
    key = (u, v) if directed else (min(u, v), max(u, v))
    return next((w for a, b, w in edges if (a, b) == key), None)


def list_weight(adjacency, u, v):
    return next((w for b, w in adjacency[u] if b == v), None)


def matrix_weight(matrix, u, v):
    return matrix[u][v]


queries = [(0, 2), (2, 0), (2, 2)]
for name, store, neighbors, weight in [
    ("edge-list", edges, edge_neighbors, edge_weight),
    ("adjacency-list", adjacency, list_neighbors, list_weight),
    ("matrix", matrix, matrix_neighbors, matrix_weight),
]:
    print(name, neighbors(store, 0), neighbors(store, 3),
          [weight(store, u, v) for u, v in queries])
    for u in range(n):
        assert sorted(neighbors(store, u)) == sorted(list_neighbors(adjacency, u))
        for v in range(n):
            assert weight(store, u, v) == matrix[u][v]

undirected = build(3, [(0, 1, 7), (1, 0, 4), (1, 1, 0)], directed=False)
assert undirected == (
    [(0, 1, 4), (1, 1, 0)],
    [[(1, 4)], [(0, 4), (1, 0)], []],
    [[None, 4, None], [4, 0, None], [None, None, None]],
)
u_edges, u_adjacency, u_matrix = undirected
for u in range(3):
    assert sorted(edge_neighbors(u_edges, u, directed=False)) == sorted(
        list_neighbors(u_adjacency, u)) == sorted(matrix_neighbors(u_matrix, u))
    for v in range(3):
        assert edge_weight(u_edges, u, v, directed=False) == list_weight(
            u_adjacency, u, v) == matrix_weight(u_matrix, u, v)
assert build(0, []) == ([], [], [])
try:
    build(2, [(0, 2, 1)])
except ValueError:
    pass
else:
    raise AssertionError("invalid endpoint accepted")
print("boundary checks: OK")
print("grid (0, 1):", list(grid_neighbors(0, 1, 2, 3)))

Sortie :

edges: [(0, 1, 4), (0, 2, 0), (1, 2, 2), (2, 2, 5)]
adjacency: [[(1, 4), (2, 0)], [(2, 2)], [(2, 5)], []]
matrix:
[None, 4, 0, None]
[None, None, 2, None]
[None, None, 5, None]
[None, None, None, None]
edge-list [(1, 4), (2, 0)] [] [0, None, 5]
adjacency-list [(1, 4), (2, 0)] [] [0, None, 5]
matrix [(1, 4), (2, 0)] [] [0, None, 5]
boundary checks: OK
grid (0, 1): [(1, 1), (0, 0), (0, 2)]

Chaque ligne de requêtes donne, dans l’ordre, les voisins sortants de 0, ceux de 3, puis les poids de 0→2, 2→0 et 2→2. Le code copie la liste d’adjacence avant de renvoyer les voisins, ce qui demande toujours de lire ses éléments linéairement. La fonction matrix_weight lit directement une case.

Pour interroger une liste d’arêtes non orientée, passer aussi directed=False, comme à build ; les listes d’adjacence et la matrice contiennent déjà les entrées inverses. L’ordre des voisins peut varier entre les représentations : les assertions utilisent donc sorted pour comparer les voisins et leurs poids.

Graphes implicites : calculer les voisins d’une grille

La fonction grid_neighbors du programme traite une grille à deux dimensions comme un graphe. Elle génère les voisins en haut, en bas, à gauche et à droite, puis garde seulement les cases à l’intérieur des limites. Toutes les cases sont accessibles ici, sans diagonale ni passage d’un bord au bord opposé. Une grille $2\times3$ a 6 sommets, $2(3-1)=4$ arêtes horizontales non orientées et $(2-1)3=3$ arêtes verticales, soit 7 arêtes. Les trois voisins de (0,1) sont (1,1), (0,0) et (0,2), comme dans la sortie.

Chaque appel vérifie au plus 4 candidats : générer les voisins prend $O(1)$ sans stocker ces 7 arêtes. Les dimensions d’une grille régulière occupent un espace constant ; des obstacles demandent aussi de stocker et de vérifier l’état des cases. Pour une grille de $R$ lignes et $C$ colonnes, BFS / DFS doit toujours conserver les sommets visités et sa file / pile, jusqu’à $O(RC)$ d’espace au pire cas. La représentation implicite économise le stockage des arêtes, pas l’état de la recherche.

On peut aussi calculer les voisins lorsque les arêtes représentent des opérations autorisées, comme un mouvement dans un puzzle. Il faut alors inclure le coût réel de génération et de validation d’un candidat dans le temps du parcours, sans le supposer toujours constant.

Représentations utilisées par les notes d’algorithmes

La vue d’ensemble des algorithmes de graphes part du problème à résoudre. Le tableau suivant décrit les besoins de stockage du code ou du pseudocode de ce site. Le chapitre d’ODS sur les parcours analyse lui aussi BFS / DFS avec des listes d’adjacence.

Note	Représentation utilisée	Raison du choix
BFS / DFS	Association entre sommets et listes de voisins ; adjacence non pondérée	Chaque sommet traité énumère ses voisins : $O(n+m)$ pour un parcours complet. Balayer les lignes d’une matrice donne $O(n^2)$ ; balayer toute la liste d’arêtes à chaque fois donne $O(n(m+1))$.
Dijkstra	Listes (voisin, poids) et tas binaire à gestion paresseuse	Seules les arêtes sortantes du sommet courant sont relâchées ; les poids doivent être positifs ou nuls. La borne générale du tas paresseux donnée dans la note est $O(n+m\log(m+1))$ ; pour un graphe simple, on retrouve $O((n+m)\log n)$.
Bellman–Ford	n indépendant et liste (u,v,w) parcourable plusieurs fois	Chaque passe relâche toutes les arêtes, sans recherche de voisins par sommet. Le pire cas est $O(n+nm)$, généralement écrit $O(nm)$ lorsque l’ensemble des arêtes est non vide.
Floyd–Warshall	Matrice de distances initialisée depuis une liste d’arêtes	Les trois boucles ont besoin des distances entre couples quelconques : $O(n^3)$ en temps et $O(n^2)$ pour la matrice.
Kruskal	Un enregistrement par arête non orientée, plus une structure union-find	Trier par poids, puis vérifier si les extrémités sont dans la même composante. Initialisation comprise, le temps vaut $O(n+m\log(m+1))$, sans index de voisins.
Prim	Listes d’adjacence pondérées symétriques et tas d’arêtes à gestion paresseuse	Lorsqu’un sommet rejoint l’arbre, ses arêtes vers l’extérieur entrent dans le tas. La forêt entière prend $O(n+m\log(m+1))$. La note présente aussi une matrice avec sélection linéaire en $O(n^2)$.

Les bornes de parcours comptent ici tous les sommets et supposent un coût constant pour les marques de visite et les accès par clé. Pour les ensembles et dictionnaires fondés sur le hachage, il faut les conditions qui assurent un coût espéré constant. Une recherche depuis un seul départ peut compter les sommets accessibles et les arêtes examinées, mais allouer des tableaux d’état pour tous les sommets ajoute toujours $O(n)$ d’initialisation. Les tas paresseux autorisent plusieurs anciennes entrées : pour des multigraphes quelconques, conserver $\log(m+1)$ au lieu de le remplacer par $\log n$.

Une matrice d’adjacence n’est pas non plus une matrice de distances. Ici, matrix[2][2]=5 indique une véritable boucle de poids 5. Floyd–Warshall initialise les distances diagonales à 0 pour les chemins sans arête, puis prend le minimum avec les poids des boucles. Il utilise l’infini pour l’absence de chemin et les poids minimaux pour les arêtes parallèles.

Les fonctions BFS / DFS de ce site attendent un dictionnaire associant chaque sommet à sa liste de voisins. Convertir les listes pondérées de l’exemple avec graph = {u: [v for v, _ in outgoing] for u, outgoing in enumerate(adjacency)} conserve aussi les sommets isolés grâce aux listes vides. BFS trouve les chemins ayant le moins d’arêtes. DFS visite les sommets accessibles, sans garantir un chemin ayant le moins d’arêtes. Les deux ignorent les poids et ne calculent donc pas les distances pondérées minimales de cet exemple.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.