C12.5 : Parcours d'un graphe en largeur

Parcours d'un graphe

Définition

Parcourir un graphe à partir d'un sommet (nœud), consiste à visiter tous les sommets possibles à partir de ce sommet.

Principe à suivre

Pour parcourir un graphe, il est nécessaire de "marquer" les sommets déjà visités pour ne pas les parcourir à nouveau.

Parcours d'un graphe en largeur

Principe du parcours en largeur

On commence par explorer un nœud source, puis ses successeurs, puis les successeurs non explorés des successeurs, etc.

Algorithme itératif

Le "marquage" des sommets va consister à :

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 ci-dessous, itérer cette fonction à la main en donnant l'état de la variable dico_dist au fur et à mesure de sa construction.

Graphe E

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.

Application : Distance entre deux sommets

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

... 
from classeGraphe import *
from foncParcoursIteratifLargeur import *

def distance(g, n1, n2):
    dico = parcours_it_larg(g, n1)
    if n2 in dico:
        return dico[n2]
    else:
        return None

# ===== Programme principal =====
# création du graphe E
graphe_E = Graphe()
graphe_E.ajout_sommet(0)
graphe_E.ajout_sommet(1)
graphe_E.ajout_sommet(2)
graphe_E.ajout_sommet(3)
graphe_E.ajout_arc(0, 1)
graphe_E.ajout_arc(0, 3)
graphe_E.ajout_arc(1, 2)
graphe_E.ajout_arc(3, 1)
# Affichage de quelques distances
print(distance(graphe_E,0,1))
print(distance(graphe_E,0,2))
print(distance(graphe_E,1,0))