De la matrice aux listes d'adjacence

Application directe du cours · niveau 1 (application) · NSI (terminale), chapitre 4 — Les graphes

Énoncé

De la matrice aux listes d'adjacence.

On dispose d'un graphe non orienté donné par sa matrice d'adjacence (liste de listes). Écrire une fonction matrice_vers_listes(M) qui renvoie le dictionnaire des listes d'adjacence correspondant. Les sommets sont numérotés de $0$ à $n - 1$ .

Corrigé

On parcourt chaque case $M [i] [j]$ ; si elle vaut $1$ , on ajoute $j$ aux voisins de $i$ .


def matrice_vers_listes(M):
    n = len(M)
    G = {i: [] for i in range(n)}
    for i in range(n):
        for j in range(n):
            if M[i][j] == 1:
                G[i].append(j)
    return G

M = [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0],
]
print(matrice_vers_listes(M))
# {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}

La complexité est $O (n^{2})$ car on examine toutes les cases de la matrice.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.