MetMat
← Retour aux méthodes

Comment représenter et parcourir un graphe en Python ?

En utilisant une matrice d'adjacence (tableau numpy 2D) pour un accès O(1)O(1) au poids d'une arête

L'objectif

Stocker un graphe dans un tableau n×nn\times n afin d'accéder instantanément à l'existence ou au poids d'une arête entre deux sommets.

Le principe

Pour un graphe à nn sommets numérotés de 00 à n−1n-1, la matrice d'adjacence MM vérifie M[i,j]=1M[i,j]=1 ssi {i,j}\{i,j\} est une arête (et M[i,j]=M[j,i]M[i,j]=M[j,i] si le graphe est non orienté) ; pour un graphe pondéré, on remplace 11 par le poids de l'arête.

La méthode
  1. 1
    Je numérote les sommets de 00 à n−1n-1 et j'initialise un tableau MM de taille n×nn\times n rempli de zéros avec np.zeros((n,n)).
  2. 2
    Pour chaque arête {i,j}\{i,j\} du graphe, je pose M[i][j] = 1 (et M[j][i] = 1 si le graphe est non orienté), ou le poids si le graphe est pondéré.
  3. 3
    Pour exploiter MM, je lis directement M[i][j] pour savoir si ii et jj sont voisins, et je compte le nombre d'arêtes par 12∑i,jM[i,j]\frac{1}{2}\sum_{i,j} M[i,j] en cas non orienté.

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.