Comment représenter et parcourir un graphe en Python ?

En utilisant un dictionnaire de listes d'adjacence pour parcourir les voisins d'un sommet

L'objectif

Représenter un graphe en Python par un dictionnaire {sommet: [voisins]} et itérer efficacement sur les voisins d'un sommet.

Le principe

À chaque sommet $s$ on associe la liste $G[s]$ de ses voisins ; pour un graphe non orienté, $t\in G[s]\Leftrightarrow s\in G[t]$ et le coût d'itération sur les voisins de $s$ est proportionnel à son degré, sans balayer les $n$ sommets.

La méthode

1
Je crée le dictionnaire G en associant à chaque sommet une liste (initialement vide ou directement remplie) de ses voisins.
2
Pour chaque arête $\{s,t\}$ , j'ajoute $t$ à G[s] et, si le graphe est non orienté, $s$ à G[t].
3
Pour parcourir les voisins d'un sommet $s$ , je boucle simplement sur G[s] ; je peux aussi écrire une fonction voisins(G, s) qui renvoie G[s].

Exemple corrigé

Difficulté croissante de 1 à 3

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.