Cas centré-sommets

Dans le cas centré-sommets, l'algorithme 9.2 comporte en fait implicitement le calcul du nombre d'arêtes du graphe (la moitié du nombre de brins). Ce calcul est effectué par les points $2$ et $3$. À l'issue du point $3$, l'accumulateur contient le nombre de brins du graphe, c'est-à-dire deux fois le nombre d'arêtes.

Lors de l'utilisation du type abstrait centré-sommets, il arrivera fréquement que nous ayons à calculer le nombre d'arêtes d'un graphe. Il est donc judicieux d'abstraire ce calcul en créant une fonction pour le faire. Nous appellerons cette fonction nb_edges(G) (en minuscules). Attention, cette opération ne fait pas partie du type abstrait mais est construite à partir des opérations du type abstrait en utilisant une boucle qui parcourt l'ensemble des sommets du graphe. Sa complexité n'est pas constante mais est $O(\vert V(G)\vert$. En voici le code Python :

def nb_edges (G):
    n = 0
    for i in range(NB_NODES(G)):
        n += NB_EDGES(NODE(G, i))
    return n / 2

La fonction average_degree s'écrit alors de manière identique au cas centré-arêtes. Mais attention, sa complexité est $O(\vert V(G)\vert$ comme celle de l'opération nb_edges(G).