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
numpy2D) pour un accès au poids d'une arêteOn 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.