Compter les morceaux d'un graphe

def produit(A, B):
    n = len(A)
    return [[sum(A[i][k] * B[k][j] for k in range(n))
             for j in range(n)] for i in range(n)]

def nb_composantes(A):
    n = len(A)
    S = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    P = [ligne[:] for ligne in S]          # P vaut A^d au tour d
    for d in range(1, n):
        P = produit(P, A)
        for i in range(n):
            for j in range(n):
                S[i][j] = S[i][j] + P[i][j]
    vus = [False] * n
    c = 0
    for i in range(n):
        if not vus[i]:
            c = c + 1                      # un morceau de plus
            for j in range(n):
                if S[i][j] > 0:
                    vus[j] = True
    return c

Pourquoi c'est correct. $S_{ij}>0$ signifie qu'il existe une chaîne de $i$ à $j$ de longueur au plus $n-1$ — et une chaîne de longueur minimale ne repasse jamais par un même sommet, donc emprunte au plus $n-1$ arêtes. Ainsi $S_{ij}>0$ équivaut à « $i$ et $j$ sont dans le même morceau ». La seconde boucle marque d'un coup tout le morceau du premier sommet non encore vu, et l'incrémente une fois.

Le point délicat. S'arrêter avant $A^{n-1}$ conclurait à tort : dans un graphe en chaîne à six sommets, aller du premier au dernier demande cinq arêtes.

Le point à retenir. Sur un graphe connexe la fonction renvoie $1$ : le critère matriciel du cours en est le cas particulier. La matrice $S$ ne dit pas seulement oui ou non — elle contient la découpe entière du graphe.