informatique (tronc commun des prépas scientifiques) · Chapitre 12 · Application directe du cours
Construire les fonctions de degré
Les graphes : modèle et représentations · niveau 1 (application)
Énoncé
Écrire la fonction degres_entrants(G) pour un graphe orienté représenté sous forme de listes d'adjacence.
Corrigé
def degres_entrants(G: dict) -> dict:
# Initialiser tous les degrés entrants à 0 pour ne pas oublier les sommets sans arcs entrants
d = {s: 0 for s in G}
for u in G:
for v in G[u]:
d[v] += 1
return dLa complexité de l'algorithme est en puisqu'il nécessite de parcourir une unique fois l'ensemble des sommets et des arcs.