De la matrice aux listes d'adjacence

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.