Construire les fonctions de degré

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 12 — Les graphes : modèle et représentations

É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 d

La complexité de l'algorithme est en $O (n + m)$ puisqu'il nécessite de parcourir une unique fois l'ensemble des sommets et des arcs.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.