26 - Graphe : parcours en largeur

⏪

⏬

⏩

1 - rappel

2 - graphe

3 - algorithme

4 - Exercices

5 - FAQ

Logiciel nécessaire pour l'activité : -

Prérequis :

Données : les 3 activités sur les Graphes
Algo : Parcours en largeur d'un Arbre

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

MODE COURS (cacher les questions)

1 - Rappel : parcours en largeur d'un arbre

⇩ ⇧ ⤊

Nous avons déjà vu la notion de parcours en largeur sur les arbres.

Le principe est

d'explorer la racine de l'arbre puis
d'explorer tous les noeuds à profondeur 1 de la racine.
d'explorer tous les noeuds à profondeur 2 de la racine.
ect... jusqu'à la plus grande profondeur

L'ordre de lecture des noeuds donne donc Alice - Bob - Clara - Didier - Eleonore...

L'algorithme consiste à :

Enfiler l'arbre dans une file
Tant que la file n'est pas vide

Défiler le prochain arbre
Explorer la racine de l'arbre
Enfiler les enfants gauche et droite de cet arbre dans la file si ce ne sont pas des arbres vides.

2 - Parcours en largeur d'un graphe

⇩ ⇧ ⤊

2.1 Principe du parcours en largeur dans un graphe

Il s'agit du même principe avec un peu plus de subtilité dans l'exploration car on risque de retomber sur des sommets que nous avons déjà rencontré : il n'y a pas de notion de hiérarchie dans un graphe et il peut y avoir des cycles.

On commence par un sommet choisi (S5 ici).

On lit les sommets autour de ce premier sommet (S1 et S9).

On s'écarte encore d'un sommet autour (S2, S3 et S8)...

Cliquez sur l'image pour lancer l'animation.

Animation du parcours — CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER

Pour faire comprendre cela à un système informatique, nous allons utiliser les attributs suivants :

un attribut couleur pour préciser l'état du sommet lors de l'exploration :

BLANC : le sommet n'a pas encore été découvert lors de l'exploration
GRIS : le sommet a été découvert
NOIR : le sommet a été traité : on a exploré toutes ses arêtes ou ses arcs sortants. Tous ses sommets adjacents sont donc découverts (ils sont donc gris ou noir)

un attribut distance qui contient le nombre d'arcs ou d'arêtes entre ce sommet et le sommet de départ. INFINI pour les sommets qui n'ont pas encore été découverts lors de l'exploration du graphe.
un attribut parent qui contient le sommet depuis lequel on a découvert ce sommet. VIDE au départ de l'exploration. Seul le sommet de départ gardera cette valeur puisqu'il est le premier.

Voici l'algorithme en français :

Pour chaque sommet u appartenant à l'ensemble S des sommets : on place BLANC dans couleur, on place INFINI dans distance, on place VIDE dans parent
On choisit un sommet de départ qu'on peint en GRIS et qui possède une distance de 0.
On enfile ce sommet de départ dans une file
Tant que la file n'est pas vide

on défile le prochain sommet qu'on nommera u
pour chaque sommet v voisin / adjacent à u :

Si v est BLANC

↦ On peint v en GRIS
↦ On définit la distance de v comme étant la distance de u + 1
↦ On définit le parent de v comme étant u
↦ On enfile v

On peint u en NOIR puisqu'on a découvert tous ses sommets adjacents si on arrive ici

Point important : notez bien qu'on agit sur les sommets v uniquement s'ils sont blancs. On ne réalise donc qu'une unique fois par sommet les actions pointées par la flèche rouge ↦.

2.2 Exemple de déroulement de l'algorithme de parcours en largeur

On considère le graphe suivant en prenant le sommet 5 comme point de départ : on cherche donc à déterminer le nombre minimum d'arêtes entre ce sommet et n'importe quel autre sommet du graphe.

Etape initiale

Image montrant la configuration initiale

On place donc une distance de 0 arête entre le sommet 5 et le sommet 5, logique. Les autres distances sont initialisées à l'infini.

On place le sommet 5 dans la file et on peut commencer.

Premier défilement

Comme la file n'est pas vide, on défile le sommet stocké dans la file. On obtient donc le sommet 5.

On fait le traitement voulu sur le sommet 5 puis on cherche dans sa matrice d'adjacence ou sa liste d'adjacence les sommets adjacents à ce sommet 5.

Imaginons qu'on obtienne la liste S1 - S9.

Deux séquences en boucle à faire :

Puisque le sommet S1 est BLANC, on le peint en GRIS, on stocke que son parent est S5 et que la distance jusqu'à S1 est donc de 0+1, soit 1. Dernière étape : on enfile S1.
Puisque le sommet S9 est BLANC, on le peint en GRIS, on stocke que son parent est S5 et que la distance jusqu'à S9 est donc de 0+1, soit 1. Dernière étape : on enfile S9.

Nous avons fini d'explorer toutes les arêtes partant du sommet S5 : on le peint en NOIR pour indiquer que nous avons totalement fini son traitement.

Deuxième défilement

Comme la file n'est pas vide, on défile le sommet stocké dans la file. On obtient donc le sommet 1.

On fait le traitement voulu sur le sommet 1 puis on cherche dans sa matrice d'adjacence ou sa liste d'adjacence les sommets adjacents à ce sommet 1.

Imaginons qu'on obtienne la liste S2 - S3 - S5.

Trois séquences en boucle à faire :

Puisque le sommet S2 est BLANC, on le peint en GRIS, on stocke que son parent est S1 et que la distance jusqu'à S5 est donc de 1+1, soit 2. Dernière étape : on enfile S2.
Puisque le sommet S3 est BLANC, on le peint en GRIS, on stocke que son parent est S1 et que la distance jusqu'à S5 est donc de 1+1, soit 2. Dernière étape : on enfile S3.
Puisque le sommet S5 n'est plus BLANC, on ne fait rien.

Nous avons fini d'explorer toutes les arêtes partant du sommet S1 : on le peint en NOIR pour indiquer que nous avons totalement fini son traitement.

Troisième défilement

Comme la file n'est pas vide, on défile le sommet stocké dans la file. On obtient donc le sommet 9.

On fait le traitement voulu sur le sommet 9 puis on cherche dans sa matrice d'adjacence ou sa liste d'adjacence les sommets adjacents à ce sommet 9.

Imaginons qu'on obtienne la liste S5 - S8.

Deux séquences en boucle à faire :

Puisque le sommet S5 n'est plus BLANC, on ne fait rien.
Puisque le sommet S8 est BLANC, on le peint en GRIS, on stocke que son parent est S9 et que la distance jusqu'à S5 est donc de 1+1, soit 2. Dernière étape : on enfile S8.

Nous avons fini d'explorer toutes les arêtes partant du sommet S9 : on le peint en NOIR pour indiquer que nous avons totalement fini son traitement.

Quatrième défilement

Comme la file n'est pas vide, on défile le sommet stocké dans la file. On obtient donc le sommet 2.

On fait le traitement voulu sur le sommet 2 puis on cherche dans sa matrice d'adjacence ou sa liste d'adjacence les sommets adjacents à ce sommet 2. Remarquez bien qu'on passe à cette distance car il n'existe plus de sommet directement adjacent à S5.

Imaginons qu'on obtienne la liste S1 - S3 - S4 - S6.

Quatre séquences en boucle à faire :

Puisque le sommet S1 n'est plus BLANC, on ne fait rien.
Puisque le sommet S3 n'est plus BLANC, on ne fait rien.
Puisque le sommet S4 est BLANC, on le peint en GRIS, on stocke que son parent est S2 et que la distance jusqu'à S5 est donc de 2+1, soit 3. Dernière étape : on enfile S4.
Puisque le sommet S6 est BLANC, on le peint en GRIS, on stocke que son parent est S2 et que la distance jusqu'à S5 est donc de 2+1, soit 3. Dernière étape : on enfile S6.

Nous avons fini d'explorer toutes les arêtes partant du sommet S2 : on le peint en NOIR pour indiquer que nous avons totalement fini son traitement.

Normalement... vous avez compris le principe.

Cinquième défilement

Sixième défilement

Septième défilement

Huitième défilement

Neuvième défilement

A partir de là, toutes les arêtes de tous les sommets ont été explorées. Nous avons donc parcouru l'intégralité du graphe.

On obtient au final :

Un Arbre dont la racine est le sommet de départ et qui mène à tous les autres sommets : cela permet de connaître UN chemin entre le sommet de départ et les autres.
La distance minimale en nombre d'arêtes entre le sommet de départ et n'importe quel autre sommet.

3.3 Questions de compréhension

✎ 01° Sur l'Arbre de parcours obtenu, quel est l'enchaînement de sommets obtenu pour aller du sommet S5 au sommet S6 ?

✎ 02° Compter le nombre d'arêtes utilisées pour aller de S5 à S6. Obtient-on bien une distance de 3 comme indiqué au dessus du sommet 6 sur le graphe ?

✎ 03° Pourquoi la distance indiquée pour S5 sur le graphe est-elle de 0 ?

04° On utilise une fois chaque sommet comme centre de recherches. Combien de fois utilise-t-on les arêtes ?

On utilise une fois chaque arête
On utilise deux fois chaque arête
On utilise trois fois chaque arête
J'aime ni les arêtes, ni le poisson

Correction ?

...CORRECTION...

On utilise les arêtes dans les deux sens. Donc deux fois.

05° Nous allons chercher la complexité de cet algorithme en prenant comme référence le nombre de fois où on teste si un sommet est BLANC. On considère uniquement un graphe connexe. Notons a le nombre d'arêtes. La complexité de cet algorithme est :

Logarithmique en fonction de a ?
Linéaire en fonction de a ?
Quadratique en fonction de a ?
Exponentielle en fonction de a ?

Correction ?

...CORRECTION...

Puisqu'on utilise deux fois les arêtes, on peut noter 𝞗(2a). Comme on ne s'intéresse pas au facteur multiplicatif, on obtient donc 𝞗(a). La bonne réponse est donc linéaire.

Le coût total d'exécution dépend en réalité du nombre de sommets et du nombre d'arêtes. Par contre, si le graphe n'est pas connexe, on peut très bien ne pas rencontrer ni traiter certains sommets et certains arcs ou arêtes.

On peut donc écrire 𝞞(s+a)

06° Donner deux chemins de distance 3 allant de S5 à S6. Quel est le parent unique de S6 sur l'Arbre de parcours obtenu ? En déduire le chemin qui va être choisi ici si on suit l'Arbre de parcours.

Correction ?

...CORRECTION...

S5-S1-S2-S6 ou S5-S9-S8-S6.

On voit sur l'Arbre qu'on obtiendrait ici le premier choix car le parent de S6 est S2.

Le parent de S2 est S1.

Le parent de S1 est S5.

07° Peut-on trouver un chemin de moins de 3 arêtes menant de S5 à S6 ?

Correction ?

...CORRECTION...

Non : le parcours en largeur donne 3. Il n'y a donc pas de chemin plus court que 3 arêtes.

Voici en image le graphe final obtenu :

Dans une activité pratique de programmation, nous verrons comment utiliser cela pour trouver automatiquement la sortie la plus proche en nombre de cases dans un labyrinthe par exemple.

3 - Algorithme de parcours en largeur

⇩ ⇧ ⤊

Algorithme du parcours en largeur

ENTREES

Un graphe noté g
Un sommet qui servira de sommet origine, noté s appartenant au graphe g

SORTIE

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

ALGORITHME PARCOURS EN LARGEUR

on initialise tous les sommets

POUR chaque sommet u appartenant au graphe g

u.couleur ← BLANC

u.distance ← INFINI

u.parent ← VIDE

Fin Pour

on initialise le sommet origine

s.couleur ← GRIS

s.distance ← 0

s.parent ← VIDE

on crée la file et on y place le sommet origine

a_traiter ← nouvelleFileVide()

enfiler(a_traiter, s)

on sort et active un sommet à la fois de la file

TANT QUE NON estVide(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 (∅)

4 - Exercices

⇩ ⇧ ⤊

Maintenant que vous avez vu l'exécution une première fois et que vous avez vu l'algorithme, il est temps de vous l'approprier.

Nous l'utiliserons dans le cadre d'un mini-projet on nous tenterons de faire sortir un personnage d'un labyrinthe, alors que des monstres rodent...

✎ 08° Fournir les listes d'adjacence des sommets ci-dessous. On placera toujours les sommets dans l'ordre alphabétique.

✎ 09° Fournir l'arbre de parcours obtenu à partir du sommet c.

✎ 10° Fournir les listes des successeurs des sommets ci-dessous. On placera toujours les sommets dans l'ordre alphabétique. Attention, cette fois le graphe est orienté.

✎ 11° Fournir l'arbre de parcours obtenu à partir du sommet c. Il faudra bien entendu ne prendre que la liste des successeurs.

✎ 12° Fournir l'arbre de parcours obtenu à partir du sommet a.

✎ 13° Fournir l'arbre de parcours obtenu à partir du sommet d.

✎ 14° Quel semble être le sommet le plus central ?

✎ 15° Le parcours en largeur fonctionne pour trouver le plus court chemin dans un graphe orienté non pondéré. Expliquez pourquoi il ne fonctionne pas pour un graphe pondéré, où le poids des arcs ou des arêtes n'est pas nécessairement 1 ?

5 - FAQ

⇩ ⇧ ⤊

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

On applique l'algorithme de Dijkstra.

Et avec un traitement naïf en Python, ça donne quoi ?

Voir

"""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 :
-> creer_graphedico_no_np(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
import math
 
# Constantes ===================================================
 
BLANC = 0
GRIS = 1
NOIR = 2
INFINI = math.inf
 
# Fonctions =====================================================
 
def creer_graphedico_no_np(g:tuple) -> dict[int, list]:
    """Renvoie un graphe-dico à partir du graphe-couple (non orienté, non pondéré)"""
 
    s, a = g                 # Désempaquetage de s et a depuis g
    graphe = {}              # Dictionnaire vide
 
    for sommet in s:         # pour chaque sommet de l'ensemble des sommets
        graphe[sommet] = []  # on crée une clé correspond au sommet menant à une liste vide
    for arete in a:          # pour chaque arête présente dans l'ensemble a
        s1, s2 = arete
        graphe[s1].append(s2)
        graphe[s2].append(s1)
 
    return graphe
 
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__":
 
    s = (0, 1, 2, 3, 4)                      # Ensemble s des sommets du graphe 
    a = ((0,1), (0,2), (1,3), (2,3), (3,4))  # Ensemble a des arêtes
    g = (s, a)                               # Graphe défini comme un couple
 
    graphe = creer_graphedico_no_np(g)
    print("Graphe en tant que dictionnaire :")
    print(graphe)
 
    parcours = largeur_d_abord_v1(graphe, 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))

Voici le résultat du programme de test précédent :



Graphe en tant que dictionnaire :
{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
 
Résultat du parcours en largeur d'abord
(0, {'couleur': 2, 'distance': 0, 'parent': None})
(1, {'couleur': 2, 'distance': 1, 'parent': 0})
(2, {'couleur': 2, 'distance': 1, 'parent': 0})
(3, {'couleur': 2, 'distance': 2, 'parent': 1})
(4, {'couleur': 2, 'distance': 3, 'parent': 3})
 
Recherche du chemin entre 0 et 3
[0, 1, 3]

Et avec un bon traitement en Python, ça donne quoi ?

Voir

"""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 :
-> creer_graphedico_no_np(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 et dans parcours
 
    # 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))

Activité publiée le 29 04 2021
Dernière modification : 29 04 2021
Auteur : ows. h.

⏪

⏫

⏩