27 - Graphe : Largeur en Python

⏪

⏬

⏩

1 - algorithme

2 - Impl.Graphe

3 - Plus simple

4 - Convertir

5 - FAQ

Logiciel nécessaire pour l'activité : -

Prérequis :

Algo : Parcours en largeur d'un Graphe

Evaluation ✎ : 01-02-03-08-09-10-11-12-13-14-15

Documents de cours : open document ou pdf

MODE COURS (cacher les questions)

1 - [rappel] Algorithme de parcours en largeur

⇩ ⇧ ⤊

(Rappel) Pseudo-code du parcours en largeur d'un graphe

Voir

Algorithme du parcours en largeur de graphe

BUT

découvrir un chemin de plus petite distance entre le sommet de départ et chaque sommet accessible.

ENTREES

Un graphe noté g
Un sommet s qui servira de sommet origine

SORTIE

Aucune ici mais on peut facilement modifier l'algorithme pour qu'il renvoie par exemple l'arbre de parcours.

ALGORITHME PARCOURS EN LARGEUR

Phase 1 d'initialisation

POUR chaque sommet u appartenant au graphe g

u.couleur ← BLANC

u.distance ← INFINI

u.parent ← VIDE

Fin Pour

s.couleur ← GRIS

s.distance ← 0

s.parent ← VIDE

a_traiter ← nouvelleFileVide()

enfiler(a_traiter, s)

Phase 2 de parcours

TANT QUE NON estFileVide(a_traiter)

u ← defiler(a_traiter)

POUR chaque sommet v appartenant à la liste d'adjacence du sommet u

SI v.couleur est BLANC

si on arrive ici, c'est que le sommet n'a pas encore été découvert

v.couleur ← GRIS

v.distance ← u.distance + 1

v.parent ← u

enfiler(a_traiter, v)

Fin Si

u.couleur ← NOIR

Fin Pour

Fin Tant Que

Renvoyer VIDE (∅)

Dans la version pseudo-code, les informations liées au parcours sont directement stockés dans les sommets.

Aucune importance tant qu'il s'agit d'une idée abstraite. Plus ennuyeux lors de l'implémentation réelle : modifier le graphe des routes à chaque fois qu'on lance le GPS n'est pas une bonne idée.

Dans les implémentations Python proposées, nous allons donc stocker les infos du parcours hors du graphe lui-même.

2 - Implémentation(s) du parcours en largeur

⇩ ⇧ ⤊

Il existe deux grandes familles d'implémentation des arêtes d'un graphe :

Par une matrice d'adjacence ;
Par des listes d'adjacence pour lesquelles de nombreuses implémentations existent.

Modèle 1: matrice d'adjacence


Matrice d'adjacence :
[[0, 1, 1, 0, 0], 
 [1, 0, 0, 1, 0], 
 [1, 0, 0, 1, 0], 
 [0, 1, 1, 0, 1], 
 [0, 0, 0, 1, 0]
]

Modèle 2 : l'ensemble des arêtes dans un tuple ( car le type enatif nsemble, set, n'est pas au programme)


Ensemble S des arêtes :
((0, 1), 
 (0, 2), 
 (1, 3),
 (2, 3),
 (3, 4)
)

Modèle 3 : listes d'adjacence dans un tableau


Listes d'adjacence stockées dans un tableau :
[[1, 2], 
 [0, 3], 
 [0, 3], 
 [1, 2, 4], 
 [3]]

Modèle 4 : listes d'adjacence dans un dictionnaire


Listes d'adjacence stockées dans un dictionnaire :
{0: [1, 2], 
 1: [0, 3], 
 2: [0, 3], 
 3: [1, 2, 4], 
 4: [3]}

Et beaucoup d'autres possibilités encore...

Il faut donc choisir une des implémentations en tant que format reconnu par notre fonction de parcours et fournir des fonctions de conversion de façon à toujours pouvoir y revenir. Sinon, il faudrait une fonction de parcours par implémentation...

Nous décidons de faire travailler nos fonctions de parcours sur des listes d'adjacences de la possibilité 4, qui ressemblent à ceci :


Listes d'adjacence stockées dans un dictionnaire :
{0: [1, 2], 
 1: [0, 3], 
 2: [0, 3], 
 3: [1, 2, 4], 
 4: [3]}

Dans le but de simplifier encore le problème, on considérera ici que les sommets ne contiennent aucune information à part leur numéro : on peut donc caractériser le graphe directement à partir de ses listes d'adjacence.

Dans la dernière partie de cette activité, vous verrez comment passer d'une implémentation à une autre en créant des fonctions de conversion adaptée.

Cela vous permettra de vous convaincre qu'implémenter un algorithme pour un modèle donné de graphe permet en réalité d'implémenter l'algorithme pour tous les modèles de graphe : il suffit de convertir les données du modèle inadapté vers le modèle choisi.

01° Considérons que le graphe g est caractérisé par ceci :


>>> graphe = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}

Questions

Quel code Python comportant une boucle permet de récupérer un à un tous les sommets depuis le dictionnaire g ?
Quel code Python comportant une boucle permet de récupérer une à une toutes les listes d'adjacence des les sommets depuis le dictionnaire g ?
Quel code Python comportant une boucle permet de récupérer un par un à la fois un sommet et sa liste d'adjacence depuis le dictionnaire g ?

Correction ?

...CORRECTION...


for sommet in g.keys():

for liste in g.values():

for sommet, liste in g.items():

02° Pour réaliser le parcours en largeur, va-t-on avoir besoin d'une File ou d'une Pile ?

Correction ?

...CORRECTION...

Une File.

03° Lire le début de la documentation de façon à vous souvenir comment utiliser facilement une File en Python.

"""Implémentation du parcours en largeur pour :
 
* un graphe implémenté avec un modèle dict  {sommet:liste d'adjacence}
* une file mutable implémentée avec un modèle deque du module collections
    -> nouvelleFile() avec file = collections.deque()
    -> enfiler()      avec file.append(x)
    -> defiler()      avec file.popleft()
    -> lireAvant()    avec file[0]
    -> estVide()      avec file
 
"""

04° Compléter la fonction de parcours largeur_d_abord_v1() de façon à la faire fonctionner correctement.

Remarque importante : les attributs du parcours ne seront pas stockés dans le graphe lui-même mais dans un dictionnaire nommé parcours.

"""Implémentation du parcours en largeur pour :
 
* un graphe implémenté avec un modèle dict  {sommet:liste d'adjacence}
* une file mutable implémentée avec un modèle deque du module collections
    -> nouvelleFile() avec file = collections.deque()
    -> enfiler()      avec file.append(x)
    -> defiler()      avec file.popleft()
    -> lireAvant()    avec file[0]
    -> estVide()      avec file
 
"""
 
# Importations =================================================
 
import collections
import math
 
# Constantes ===================================================
 
BLANC = 0
GRIS = 1
NOIR = 2
INFINI = math.inf
 
# Fonctions =====================================================
 
def largeur_d_abord_v1(g:'dict[int, list]', s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    parcours = {}
 
    # on initialise tous les sommets
    for sommet in g.keys():
        parcours[sommet] = {}
        parcours[...]['couleur'] = ...
        parcours[...]['distance'] = ...
        parcours[...]['parent'] = ...
 
    # on initialise le sommet de départ
    parcours[...]["couleur"] = ...
    parcours[...]["distance"] = ...
 
    # on crée la file et on y place le sommet origine
    a_traiter = collections.deque()  # on crée un nouvelle file muable
    ...              # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:   # tant que la file des sommets à traiter n'est pas vide
        u = ...        # on défile le prochain sommet à traiter
        for ... in ...:   # pour chaque sommet v dans la liste d'adjacence de u
            if parcours[...]["couleur"] == ...:
                parcours[...]["couleur"] = ...
                parcours[...]["distance"] = ...
                parcours[...]["parent"] = ...
                ...
        parcours[...]["couleur"] = ...
 
    # on renvoie le résultat du parcours
    return ...
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    reponse = []
 
    if sommet_initial in parcours.keys() and sommet_final in parcours.keys():
        sommet = sommet_final
        while sommet is not None:
            reponse.append(sommet)
            sommet = parcours[sommet]['parent']
 
    inversion = []
    while reponse:
        inversion.append(reponse.pop())
    return inversion
 
 
# Programme principal =================================================
 
if __name__ == "__main__":
 
    graphe = {
        0: [1, 2], 
        1: [0, 3], 
        2: [0, 3], 
        3: [1, 2, 4], 
        4: [3]
    }
     
    parcours = largeur_d_abord_v1(graphe, 0)
     
     
    # Phase d'affichage pur
    print("Graphe en tant que dictionnaire :")
    print(graphe)
    print("\nRésultat du parcours en largeur d'abord")
    for couple in parcours.items():
        print(couple)
    print("\nRecherche du chemin entre 0 et 3")
    print(donner_chemin(0, 3, parcours))

Correction ?

...CORRECTION...

"""Implémentation du parcours en largeur pour :
 
* un graphe implémenté sous forme d'un graphe-dico  {sommet:liste d'adjacence}
* une file muable implémentée via la classe Deque du module collections
    -> nouvelleFile() avec file = collections.deque()
    -> enfiler()      avec file.append(x)
    -> defiler()      avec file.popleft()
    -> lireAvant()    avec file[0]
    -> estVide()      avec file
 
"""
 
# Importations =================================================
 
import collections
import math
 
# Constantes ===================================================
 
BLANC = 0
GRIS = 1
NOIR = 2
INFINI = math.inf
 
# Fonctions =====================================================
 
def largeur_d_abord_v1(g:'dict[int, list]', s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    parcours = {}
 
    # on initialise tous les sommets
    for sommet in g.keys():
        parcours[sommet] = {}
        parcours[sommet]['couleur'] = BLANC
        parcours[sommet]['distance'] = INFINI
        parcours[sommet]['parent'] = None
 
    # on initialise le sommet de départ
    parcours[s]["couleur"] = GRIS
    parcours[s]["distance"] = 0
 
    # on crée la file et on y place le sommet origine
    a_traiter = collections.deque()  # on crée un nouvelle file muable
    a_traiter.append(s)              # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:   # tant que la file des sommets à traiter n'est pas vide
        u = a_traiter.popleft()        # on défile le prochain sommet à traiter
        for v in g[u]:   # pour chaque sommet v dans la liste d'adjacence de u
            if parcours[v]["couleur"] == BLANC:
                parcours[v]["couleur"] = GRIS
                parcours[v]["distance"] = parcours[u]["distance"] + 1
                parcours[v]["parent"] = u
                a_traiter.append(v)
        parcours[u]["couleur"] = NOIR
 
    # on renvoie le résultat du parcours
    return parcours
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    reponse = []
 
    if sommet_initial in parcours.keys() and sommet_final in parcours.keys():
        sommet = sommet_final
        while sommet is not None:
            reponse.append(sommet)
            sommet = parcours[sommet]['parent']
 
    inversion = []
    while reponse:
        inversion.append(reponse.pop())
    return inversion
 
 
# Programme principal =================================================
 
if __name__ == "__main__":
 
    graphe = {
        0: [1, 2], 
        1: [0, 3], 
        2: [0, 3], 
        3: [1, 2, 4], 
        4: [3]
    }
     
    parcours = largeur_d_abord_v1(graphe, 0)
     
     
    # Phase d'affichage pur
    print("Graphe en tant que dictionnaire :")
    print(graphe)
    print("\nRésultat du parcours en largeur d'abord")
    for couple in parcours.items():
        print(couple)
    print("\nRecherche du chemin entre 0 et 3")
    print(donner_chemin(0, 3, parcours))

05° Expliquer comment fonctionne la fonction donner_chemin() qui permet de récupérer le chemin le plus court entre deux sommets. Pour cela, expliquer en français ce qu'on réalise ligne par ligne.

3 - Plus simple

⇩ ⇧ ⤊

On peut en réalité se passer de la gestion des couleurs.

3 Gérer les couleurs (sans les couleurs) en Python

Voir

Gestion de BLANC ou (GRIS/NOIR)

Rajoutons un tableau decouverts qui liste les sommets découverts : dès qu'on découvre un nouveau sommet, on le place dans ce tableau.

On en déduit ceci :

Un sommet est BLANC s'il n'est pas dans decouverts.
Un sommet est GRIS ou NOIR s'il est dans decouverts.

Distinguer GRIS et NOIR

Il faut utiliser le contenu de la File des sommets a_traiter : c'est une File, normalement nous ne devrions pas pouvoir lire son contenu. Mais si on l'implémente avec un type deque ou un type list, nous pouvons bien entendu savoir si un élément est dedans, ou pas. Par contre, c'est à coût linéaire attention.

Un sommet est BLANC s'il n'est pas dans decouverts.
Un sommet est GRIS s'il est dans decouverts ET a_traiter.
Un sommet est NOIR s'il est dans decouverts MAIS PAS dans a_traiter.

06° Compléter la fonction de parcours largeur_d_abord_v2() de façon à la faire fonctionner correctement sans gestion directe de la COULEUR :

"""Implémentation du parcours en largeur pour :
 
* un graphe implémenté sous forme d'un graphe-dico  {sommet:liste d'adjacence}
* une file muable implémentée via la classe deque du module collections
    -> nouvelleFile() avec file = collections.deque()
    -> enfiler()      avec file.append(x)
    -> defiler()      avec file.popleft()
    -> lireAvant()    avec file[0]
    -> estVide()      avec file
 
"""
 
# Importations =================================================
 
import collections
 
 
# 2 - déclaration des fonctions ================================
 
def largeur_d_abord_v2(g:'dict[int, list]', s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    decouverts = []              # on initialise la liste des sommets découverts
    parcours = {}                # on initialise le dict des infos sur le parcours
 
    # on initialise le sommet de départ
    decouverts.append(s)         # on signale qu'on a découvert ce sommet
    parcours[s] = {}
    parcours[s]["distance"] = 0   # et qu'il est à distance 0 de lui-même
    parcours[s]["parent"] = None  # et qu'il est la racine de l'arbre de parcours
 
    # on crée la file et on y place le sommet origine
    a_traiter = ...          # on crée un nouvelle file muable illimitée en taille
    ...          # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:             # tant que la file des sommets à traiter n'est pas vide
        u = ...  # on défile le prochain sommet u à traiter
        for ... in g[u]:           # pour chaque sommet v dans la liste d'adjacence de u
            if v not in ...:             # si v n'est pas encore decouvert
                ...           # dire que v est découvert
                parcours[v] = {}
                parcours[...]["distance"] = ...
                parcours[...]["parent"] = ...
                ...             # on rajoute v dans la file des sommets à traiter
        # à partir d'ici u est NOIR car dans decouvert mais plus dans a_traiter
 
    # on renvoie le résultat du parcours
    return parcours
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    reponse = []
 
    if sommet_initial in parcours.keys() and sommet_final in parcours.keys():
        sommet = sommet_final
        while sommet is not None:
            reponse.append(sommet)
            sommet = parcours[sommet]['parent']
 
    inversion = []
    while reponse:
        inversion.append(reponse.pop())
    return inversion
 
 
# Programme de test =================================================
 
if __name__ == "__main__":
 
    graphe_test = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
 
    print("Graphe en tant que dictionnaire :")
    print(graphe_test)
 
    parcours = largeur_d_abord_v2(graphe_test, 0)
    print("\nRésultat du parcours en largeur d'abord")
    for couple in parcours.items():
        print(couple)
 
    print("\nRecherche du chemin entre 0 et 3")
    print(donner_chemin(0, 3, parcours))

Correction ?

...CORRECTION...

"""Implémentation du parcours en largeur pour :
 
* un graphe implémenté sous forme d'un graphe-dico  {sommet:liste d'adjacence}
* une file muable implémentée via la classe deque du module collections
    -> nouvelleFile() avec file = collections.deque()
    -> enfiler()      avec file.append(x)
    -> defiler()      avec file.popleft()
    -> lireAvant()    avec file[0]
    -> estVide()      avec file
 
Le module comporte les fonctions :
-> transtyper_graphe_tuple_en_dict(g:tuple) -> dict[int, list]
-> largeur_d_abord_v1(g:dict[int, list], s:int) -> dict
-> donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list
 
"""
 
# Importations =================================================
 
import collections
 
 
# 2 - déclaration des fonctions ================================
 
def largeur_d_abord_v2(g:'dict[int, list]', s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    decouverts = []              # on initialise la liste des sommets découverts
    parcours = {}                # on initialise le dict des infos sur le parcours
 
    # on initialise le sommet de départ
    decouverts.append(s)         # on signale qu'on a découvert ce sommet
    parcours[s] = {}
    parcours[s]["distance"] = 0   # et qu'il est à distance 0 de lui-même
    parcours[s]["parent"] = None  # et qu'il est la racine de l'arbre de parcours
 
    # on crée la file et on y place le sommet origine
    a_traiter = collections.deque()          # on crée un nouvelle file muable illimitée en taille
    a_traiter.append(s)          # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:             # tant que la file des sommets à traiter n'est pas vide
        u = a_traiter.popleft()  # on défile le prochain sommet u à traiter
        for v in g[u]:           # pour chaque sommet v dans la liste d'adjacence de u
            if v not in decouverts:             # si v n'est pas encore decouvert
                decouverts.append(v)            # dire que v est découvert
                parcours[v] = {}
                parcours[v]["distance"] = parcours[u]["distance"] + 1
                parcours[v]["parent"] = u
                a_traiter.append(v)             # on rajoute v dans la file des sommets à traiter
        # à partir d'ici u est NOIR car dans decouvert mais plus dans a_traiter
 
    # on renvoie le résultat du parcours
    return parcours
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    reponse = []
 
    if sommet_initial in parcours.keys() and sommet_final in parcours.keys():
        sommet = sommet_final
        while sommet is not None:
            reponse.append(sommet)
            sommet = parcours[sommet]['parent']
 
    inversion = []
    while reponse:
        inversion.append(reponse.pop())
    return inversion
 
 
# Programme de test =================================================
 
if __name__ == "__main__":
 
    graphe_test = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
 
    print("Graphe en tant que dictionnaire :")
    print(graphe_test)
 
    parcours = largeur_d_abord_v2(graphe_test, 0)
    print("\nRésultat du parcours en largeur d'abord")
    for couple in parcours.items():
        print(couple)
 
    print("\nRecherche du chemin entre 0 et 3")
    print(donner_chemin(0, 3, parcours))

07° Réaliser cette troisième version qui ne sert à rien mais qui affiche simplement le nom des sommets découverts au fur et à mesure de l'exploration. Il s'agit d'une version simplifiée de la fonction précédente. Tentez de le faire seul, aller voir uniquement l'algorithme du parcours en largeur au besoin, sans regarder directement le code Python de la question précédente.

Inutile donc de créer un dictionnaire stockant les informations obtenues lors du parcours. C'est une fonction qui ne sert à rien : elle ne fait qu'afficher le sommet découvert.

...
 
def largeur_d_abord_v3(g:'dict[int, list]', s:int) -> None:
    """Affiche le numéro des sommets rencontrés lors de l'exploration"""
 
    pass
 
...

Correction ?

...CORRECTION...

...
 
def largeur_d_abord_v3(g:'dict[int, list]', s:int) -> None:
    """Affiche le numéro des sommets rencontrés lors de l'exploration"""
 
    decouverts = []              # on initialise la liste des sommets découverts
 
    # on initialise le sommet de départ
    decouverts.append(s)         # on signale qu'on a découvert ce sommet
 
    # on crée la file et on y place le sommet origine
    a_traiter = collections.deque()          # on crée un nouvelle file muable illimitée en taille
    a_traiter.append(s)          # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:             # tant que la file des sommets à traiter n'est pas vide
        u = a_traiter.popleft()  # on défile le prochain sommet u à traiter    
        print(u)
        for v in g[u]:           # pour chaque sommet v dans la liste d'adjacence de u
            if v not in decouverts:             # si v n'est pas encore decouvert
                decouverts.append(v)            # dire que v est découvert  
                a_traiter.append(v)             # on rajoute v dans la file des sommets à traiter
        # à partir d'ici u est NOIR car dans decouvert mais plus a_traiter
 
...

08° Modifier votre dernière fonction : nous voudrions utiliser la "File du pauvre" basée sur un type list et utilisant append() et pop(0).

On rappelle que cette version n'est pas une bonne version car le défilement est alors à coût linéaire. Mais c'est pratique pour un prototype.

Correction ?

...CORRECTION...

...
 
def largeur_d_abord_v3(g:'dict[int, list]', s:int) -> None:
    """Affiche le numéro des sommets rencontrés lors de l'exploration"""
 
    decouverts = []              # on initialise la liste des sommets découverts
 
    # on initialise le sommet de départ
    decouverts.append(s)         # on signale qu'on a découvert ce sommet
 
    # on crée la file et on y place le sommet origine
    a_traiter = []          # on crée un nouvelle file muable illimitée en taille
    a_traiter.append(s)          # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:             # tant que la file des sommets à traiter n'est pas vide
        u = a_traiter.pop(0)  # on défile le prochain sommet u à traiter    
        print(u)
        for v in g[u]:           # pour chaque sommet v dans la liste d'adjacence de u
            if v not in decouverts:             # si v n'est pas encore decouvert
                decouverts.append(v)            # dire que v est découvert  
                a_traiter.append(v)             # on rajoute v dans la file des sommets à traiter
        # à partir d'ici u est NOIR car dans decouvert mais plus a_traiter
 
...

09° Modifier votre graphe de façon à l'agrandir un peu. Vérifier que vos fonctions de parcours en version 1 et 2 fonctionnent encore.

Enfin, rajouter quelques sommets de façon à rendre le graphe non-connexe : il doit être composé de deux sous-graphes qui ne se peuvent pas communiquer entre eux. Question : le parcours en largeur partant d'un côté permet-il d'apprendre des choses sur l'autre côté ?

4 - Passage d'une implémentation à une autre

⇩ ⇧ ⤊

Les graphes dont a besoin notre algorithme est un graphe de modèle dict[int, list]

Par exemple :


{0: [1, 2], 
 1: [0, 3], 
 2: [0, 3], 
 3: [1, 2, 4], 
 4: [3]
}

Mais notre algorithme reste applicable quel que soit le modèle de votre graphe. Il suffira de transtyper votre graphe en dict[int, list] comme nous l'avons vu dans la partie Données.

5 - FAQ

⇩ ⇧ ⤊

Et on fait comment sur un graphe pondéré ?

On applique l'algorithme de Dijkstra.

Pas au programme donc exploitable à loisir pour le Grand Oral.

Activité publiée le 09 04 2024
Dernière modification : 09 04 2024
Auteur : ows. h.

⏪

⏫

⏩