Deux représentations d'un graphe

def matrice_vers_listes(A):
    return {i: [j for j in range(len(A)) if A[i][j]]
            for i in range(len(A))}

def listes_vers_matrice(D):
    n = len(D)
    A = [[0] * n for _ in range(n)]
    for i in D:
        for j in D[i]:
            A[i][j] = 1
    return A

Les deux sont réciproques sur les graphes simples : partir d'une matrice, la convertir et revenir redonne la matrice de départ. On peut le tester en une ligne : listes_vers_matrice(matrice_vers_listes(A)) == A.

Ce qu'on gagne et ce qu'on perd. La matrice occupe $n^2$ cases quel que soit le nombre d'arêtes, et répond en $O(1)$ à « $i$ et $j$ sont-ils voisins ? ». Les listes occupent une place proportionnelle au nombre d'arêtes — un avantage décisif sur les graphes creux, comme les réseaux routiers — et donnent les voisins d'un sommet immédiatement, mais répondent en $O(\mathrm{deg}i)$ à la question précédente.

Une limite. Ces conversions perdent les poids : elles ne valent que pour un graphe non pondéré. Avec des poids, il faudrait remplacer la liste par une liste de couples $(voisin,poids)$.