Algo Graphe Largeur

Identification

Infoforall

24 - Graphe : parcours en largeur


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

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
Parcours en largeur

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

L'algorithme consiste à :

  1. Enfiler l'arbre dans une file
  2. Tant que la file n'est pas vide
    1. Défiler le prochain arbre
    2. Explorer la racine de l'arbre
    3. Enfiler les enfants gauche et droite de cet arbre dans la file si ce ne sont pas des arbres vides.

Avant de commencer l'activité, allez regarder cette vidéo YouTube (20 minutes) qui vous montre tout l'intérêt de savoir naviguer dans les graphes :

graphe et réseau social

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 hierarchie 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
CLIQUEZ SUR L'IMAGE POUR LANCER L'ANIMATION

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 :
    1. BLANC : le sommet n'a pas encore été découvert lors de l'exploration
    2. GRIS : le sommet a été découvert
    3. 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 :

  1. 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
  2. On choisit un sommet de départ qu'on peint en GRIS et qui possède une distance de 0.
  3. On enfile ce sommet de départ dans une file
  4. Tant que la file n'est pas vide
    1. on défile le prochain sommet qu'on nommera u
    2. 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
    3. 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 :

  1. 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 éape : on enfile S1.
  2. 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.
Exploration de S5

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 :

  1. 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 éape : on enfile S2.
  2. 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.
  3. Puisque le sommet S5 n'est plus BLANC, on ne fait rien.
Exploration de S1

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 :

  1. Puisque le sommet S5 n'est plus BLANC, on ne fait rien.
  2. 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 éape : on enfile S8.
Exploration de S9

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 :

  1. Puisque le sommet S1 n'est plus BLANC, on ne fait rien.
  2. Puisque le sommet S3 n'est plus BLANC, on ne fait rien.
  3. 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 éape : on enfile S4.
  4. 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 éape : on enfile S6.
Exploration de S2

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

Exploration de S3

Sixième défilement

Exploration de S8

Septième défilement

Exploration de S4

Huitième défilement

Exploration de S6

Neuvième défilement

Exploration de S7

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.
Etat final

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é 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...

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 convexe. 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...

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 convexe, 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...

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...

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 :

Etat final

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

    fnouvelleFileVide()

    enfiler(f, s)

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

    TANT QUE NON estVide(f)

      udefiler(f)

      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(f, 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.

Arbre de l'exercice

✎ 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é.

graphe 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.

Il nous reste à voir le parcours en profondeur et la recherche de cycle.

Nous verrons ensuite en pratique comment mettre tout ceci en machine pour résoudre des problèmes.

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