C12.5 : Parcours d'un graphe en largeur

Le parcours en largeur d'abord consiste à :

• - attribuer la valeur 0 au sommet de départ,
• - attribuer la valeur 1 aux voisins du sommet de départ,
• - attribuer la valeur 2 aux voisins des voisins du sommet de départ (sauf s'ils ont été déjà vus),
• - ...

Voici la fonction proposée :

def parcours_it_larg(g, s0):
    "parcours en large d'abord d'un graphe g depuis un sommet s"
    dico_dist = {s0: 0}
    liste_en_cours = [s0]
    liste_suivants = []
    while len(liste_en_cours) > 0:
        s = liste_en_cours.pop()
        for voisin in g.liste_voisins(s):
            if voisin not in dico_dist:
                liste_suivants.append(voisin)
                dico_dist[voisin] = dico_dist[s] + 1
        if len(liste_en_cours) == 0:
            liste_en_cours = list(liste_suivants)
            liste_suivants = []
    return dico_dist

1) Cette fonction est-elle récursive ?

2) Successivement pour chacun des sommets du graphe suivant, itérer cette fonction à la main en donnant l'état de la variable dico_dist au fur et à mesure de sa construction.

3) A quoi correspond la variable dico_dist ?

4) Ajouter des commentaires dans le code de la fonction.

5) En une phrase, expliquer pourquoi on parle d'un parcours en largeur d'abord.

6) Écrire le code du programme qui utilise cette fonction pour renvoyer la distance (ou None s'il n'y a pas de chemin) entre deux nœuds d'un graphe.