Comment représenter et parcourir un graphe en Python ? | MetMat

Comment représenter et parcourir un graphe en Python ?

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

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

Que ferais-tu face à un exercice de ce type ?

Coder en Python le graphe non orienté à $4$ sommets dont les arêtes sont $\{0,1\}$ , $\{0,2\}$ , $\{1,2\}$ , $\{2,3\}$ , puis compter le nombre total d'arêtes.

L'objectif

Stocker un graphe dans un tableau $n\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 à $n$ sommets numérotés de $0$ à $n-1$ , la matrice d'adjacence $M$ vérifie $M[i,j]=1$ ssi $\{i,j\}$ est une arête (et $M[i,j]=M[j,i]$ si le graphe est non orienté) ; pour un graphe pondéré, on remplace $1$ par le poids de l'arête.

La méthode

1
Je numérote les sommets de $0$ à $n-1$ et j'initialise un tableau $M$ de taille $n\times n$ rempli de zéros avec np.zeros((n,n)).
2
Pour chaque arête $\{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
Pour exploiter $M$ , je lis directement M[i][j] pour savoir si $i$ et $j$ sont voisins, et je compte le nombre d'arêtes par $\frac{1}{2}\sum_{i,j} M[i,j]$ en cas non orienté.

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Coder en Python le graphe non orienté à $4$ sommets dont les arêtes sont $\{0,1\}$ , $\{0,2\}$ , $\{1,2\}$ , $\{2,3\}$ , puis compter le nombre total d'arêtes.

Étape 1 —

Je numérote les sommets de

0

n-1

et j'initialise un tableau

M

de taille

n\times n

rempli de zéros avec np.zeros((n,n)).

Je numérote les sommets $0,1,2,3$ et j'initialise la matrice de zéros.

import numpy as np
n = 4
M = np.zeros((n, n))

Étape 2 —

Pour chaque arête

\{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é.

J'ajoute chaque arête symétriquement.

aretes = [(0,1), (0,2), (1,2), (2,3)]
for i, j in aretes:
    M[i][j] = 1
    M[j][i] = 1

Étape 3 —

Pour exploiter

M

, je lis directement M[i][j] pour savoir si

i

j

sont voisins, et je compte le nombre d'arêtes par

\frac{1}{2}\sum_{i,j} M[i,j]

en cas non orienté.

Je compte les arêtes en sommant $M$ puis en divisant par $2$ .

nb_aretes = int(M.sum() / 2)
print(nb_aretes)  # 4

Le graphe comporte $4$ arêtes.

Application guidée

Écrire une fonction degre(M, s) qui renvoie le degré du sommet $s$ dans un graphe non orienté codé par sa matrice d'adjacence $M$ .

Application autonome 1

Coder un graphe pondéré à $3$ sommets avec les arêtes $\{0,1\}$ de poids $5$ , $\{1,2\}$ de poids $2$ , $\{0,2\}$ de poids $7$ , puis afficher le poids entre $0$ et $2$ .

Application autonome 2

Écrire une fonction voisins(M, s) qui renvoie la liste des voisins du sommet $s$ dans un graphe non orienté codé par sa matrice d'adjacence M (tableau numpy 2D).

Application autonome 3

Tester si un graphe non orienté codé par sa matrice d'adjacence M est un graphe complet (tous les sommets distincts sont reliés).

Crée ton compte pour accéder à la fiche et aux exercices

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

Pour comprendre, fais des exercices !

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