Comment représenter et parcourir un graphe en Python ?

Choisir une structure de données adaptée (matrice d'adjacence ou dictionnaire de listes) pour coder un graphe et en explorer les arêtes et voisinages.

Choisissez une approche :

En utilisant une matrice d'adjacence (tableau numpy 2D) pour un accès $O(1)$ au poids d'une arête
On code un graphe à $n$ sommets par un tableau $M\in\mathcal{M}_n(\mathbb{R})$ où $M[i,j]$ vaut $1$ (ou le poids) si $\{i,j\}$ est une arête, et $0$ sinon.
En utilisant un dictionnaire de listes d'adjacence pour parcourir les voisins d'un sommet
On représente un graphe par un dictionnaire associant à chaque sommet la liste de ses voisins, ce qui rend l'itération sur les voisins directe et économique en mémoire pour les graphes peu denses.